CombinationSumIV.java

package dynamic_programming;

import java.util.Arrays;

/**
 * Created by gouthamvidyapradhan on 17/12/2017.
 * Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that
 * add up to a positive integer target.

 Example:

 nums = [1, 2, 3]
 target = 4

 The possible combination ways are:
 (1, 1, 1, 1)
 (1, 1, 2)
 (1, 2, 1)
 (1, 3)
 (2, 1, 1)
 (2, 2)
 (3, 1)

 Note that different sequences are counted as different combinations.

 Therefore the output is 7.
 Follow up:
 What if negative numbers are allowed in the given array?
 How does it change the problem?
 What limitation we need to add to the question to allow negative numbers?

 Solution: Backtrack and dp
 */
public class CombinationSumIV {

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        int[] A = {1, 2, 3};
        System.out.println(new CombinationSumIV().combinationSum4(A, 4));
    }

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return backtrack(nums, dp, target);
    }

    private int backtrack(int[] nums, int[] dp, int sum){
        int total = 0;
        if(sum < 0) return 0;
        if(dp[sum] != -1) return dp[sum];
        else{
            for (int num : nums) {
                total += backtrack(nums, dp, sum - num);
            }
        }
        dp[sum] = total;
        return dp[sum];
    }

}