CombinationSumIV377.java

/**
 * 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?
 */


public class CombinationSumIV377 {
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || target < 0) return 0;
        int N = nums.length;
        int[][] dp = new int[N + 1][target + 1];
        for (int i=0; i<=N; i++) {
            dp[i][0] = 1;
        }
        for (int i=1; i<=N; i++) {
            int n = nums[i-1];
            for (int j=1; j<=target; j++) {
                int local = 0;
                for (int k=1; k<i; k++) {
                    local += j < nums[k-1] ? 0 : (dp[i][j - nums[k-1]] - dp[i-1][j - nums[k-1]]);
                }
                dp[i][j] = local + (j < n ? 0 : dp[i][j - n]) + dp[i-1][j];
            }
        }
        return dp[N][target];
    }


    /**
     * https://leetcode.com/problems/combination-sum-iv/discuss/85036/1ms-Java-DP-Solution-with-Detailed-Explanation
     */
    private int[] dp;
    public int combinationSum42(int[] nums, int target) {
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(nums, target);
    }
    
    private int helper(int[] nums, int target) {
        if (dp[target] != -1) {
            return dp[target];
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                res += helper(nums, target - nums[i]);
            }
        }
        dp[target] = res;
        return res;
    }


    public int combinationSum43(int[] nums, int target) {
        int[] comb = new int[target + 1];
        comb[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int n: nums) {
                if (i - n >= 0) {
                    comb[i] += comb[i - n];
                }
            }
        }
        return comb[target];
    }

}