Data Structures and Algorithms in Java – Dynamic Programming – Combination Sum

Problem:

Given an array of numbers and a target number , find in how many ways the numbers in the input array can be summed up to form the target number.

For example,

Given the input:

[1,2,3]

and the target 4

The output should be

7

since :

1 + 1 + 1 + 1 = 4

1 + 2 + 1 = 4

1 + 1 + 2 = 4

1 + 3 = 4

2 + 1 + 1 = 4

2 + 2 = 4

3 + 1 = 4

Try out the solution here:

https://leetcode.com/problems/combination-sum-iv

Solution:

Hint:

• For every element in the input , pick one element and then find the combination for the remaining (target – input[i]) recursively

Let’s take the same example to understand this:

[1,2,3]

Target : 4

Step 1:

Let’s pick the first element 1.

So the combination at this step is [1]

Now the remaining target is target – 1 = 4 – 1 = 3

For this remaining 3 , again you can pick any value from the input which is less than or equal to 3.

Step 2:

For the current target 3 , again pick 1 from the given input.

So the combination at this step is [1,1]

Now the remaining target is target – 1 = 3 -1 = 2

For this remaining 2 , again you can pick any value from the input which is less than or equal to 2.

Step 3:

For the current target 2, again pick 1 from the input.

So the combination at this step is [1,1,1]

Now the remaining target is target – 1 = 2 -1 = 1

For this remaining 1 , again you can pick any value from the input which is less than or equal to 1.

Step 4:

For the current target 1 , again pick 1 from the input.

So the combination at this step is [1,1,1,1]

Now the remaining target is 0.

And we have found out one possible combination!

We picked only the value 1 all along the way.

If in step 2 we had picked up 2 instead of 1 , the then combination would have been [1,2] and the remaining target would have been 3 -2 = 1. Again for the remaining 1 you would continue the same step and the target would be 0 in the next step giving the combination [1,2,1].

So for every target , you need to make a recursive call with (target – current value chosen for the combination)

This is a recursive solution and has exponential time complexity.

Here is the code :

class Solution{

    public int combinationSum(int[] nums,int target){

          if(target == 0 ) return 0;
            int count = 0;
          for(int i = 0 ;i < nums.length ; i++){
                 if(target >= nums[i]){
                   count + = combinationSum(nums,target - nums[i]);    
                }

           }

      return count;
       
   }

}

A better solution is to avoid repeated recurring calls if the sub solution is already calculated.

You can refactor the above recursive solution this way:

ALGORITHM:

STEP1: Initialize a global array of the target size + 1 to store the combination values for each value which can make up the target value ( 1 to target value) .

STEP 2: Set the value -1 to all the values in the array . The value 0 means there is no combination for the particular value so use a negative value instead.

STEP 3: Initialize combination for the value 0 as 1

STEP 4: For every number upto the target , check the combination for each input value recursively and store it in the global array at the respective index. If the value is already calculated return it from the array instead of the recursive call

STEP 5: Return the final value of the global array which has the total number of combinations

Code:

class Solution {
    
     int[] dp ;
        
     
    public int combinationSum4(int[] nums, int target) {
        dp =  new int[target+1];
           Arrays.fill(dp,-1);
        dp[0] = 1;
       
        
        return find(nums,target);
    }
    
    
    public int find(int[] nums,int target){
        
        
        if(dp[target]!=-1){
            
            return dp[target];
        }
        
        int count = 0;
        for(int i=0;i<nums.length;i++){
            
            if(target >= nums[i]){
            count = count + find(nums,target-nums[i]);
            }
        }
        
        dp[target] = count;
        
        return count;
    }
}

This is a top down approach since we start from the target and then make recursive calls for lesser numbers (target – nums[i]) until we reach 0.

You can start from the lowest value 1 instead and keep building the combination until you reach the target (4 in the example).

Here is the code:

class Solution{

     public int combinationSum4(int[] nums,int target){
                 int[] dp = new int[target+1];
                 dp[0] = 1;
             for(int i=1;i<=target;i++){

                   for(int j=0;j<i;j++){
                         
                        if(nums[j] <= i ){
                             dp[i] = dp[i]+dp[i-nums[j]];
                              }
                       }
              }
          return dp[target];        
    }

}

Time complexity of the above algorithm is O(n * m ) where n is the target and m is the input array length.

Space complexity is O(n) to store the output array.