Combination Sum IV

题目
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?

答案

class Solution {
    int[] dp = null;
    public int combinationSum4(int[] nums, int target) {
        if(target == 0) return 1;
        
        int ans = 0;
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        recur(nums, target);
        return dp[target];
    }
    
    public int recur(int[] nums, int target) {
        // if(target == 0) return 1; This line is not needed if you have initilized dp[0] = 1
        if(dp[target] != -1) return dp[target];
        
        int ans = 0;
        for(int i = 0; i < nums.length; i++) {
            if(target >= nums[i]) {
                ans += recur(nums, target - nums[i]);                
            }
        }
        
        dp[target] = ans;
        return ans;
    }
}

Negative numbers can't be allowed in current question, because it would produce infinite number of combinations, because the length of a combination could be infinite

For example, with [-1,1], target = 1, you can have infinite many combinations that sum to target = 1

So, we really need to limit the problem to only find number of combinations of length < maxlen that sum to some target.

Use dp[i] to keep track of the map(length -> number of combinations)

class Solution {
    
    Map<Integer, Map<Integer, Integer>> dp_map = new HashMap<Integer, Map<Integer, Integer>>();

    public int combinationSum4(int[] nums, int target, int maxlen) {
        if(num == null || nums.length == 0 || maxlen <= 0) return 0;
        return recur(nums, 0, target, maxlen);
    }
    
    public int recur(int[] nums, int len, int target, int maxlen) {
        // Base cases
        if(len > maxlen) return 0;
        
        // Memorized values
        if(map.get(target) != null && map.get(target).containKeys(len))
            map.get(target).get(key);
        
        // Recursive cases
        
        int ans = 0;
        // If target is 0, there is at least 1 combination, namely the empty set {}
        if(target == 0) ans++;
        
        for(int i = 0; i < nums.length; i++) {
            ans += recur(nums, len + 1, target - nums[i], maxlen);
        }
        
        Map<Integer, Integer> len2combos = dp_map.get(target);
        if(len2combos == null) {
            len2combos = new HashMap<Integer, Integer>();
            dp_map.put(target, len2combos);
        }
        len2combos.put(len, ans);
        return ans;
    }
}