377. Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 1000

• All the elements of nums are unique.

• 1 <= target <= 1000

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:

Version 1: DP

backPack VI 和combination sum IV是同一题 本质上是背包问题，但是和BP IV又不一样，因为同一组数可以组成不同的组合 比如1, 1, 2和1, 2, 1在本题是两个解，所以j循环要放在外面，使得相同的一组数 有可能出现在不同的结果中

典型的完全背包问题(518. Coin Change 2)。 如果 数相同 顺序不同 被认为是 不同 的答案，那么就先循环背包容量，再循环物品。 如果 数相同 顺序不同 被认为是 相同 的答案，那么就先循环物品，再循环背包容量。

所以只要把(BP IV)中j循环翻出来即可： BP IV: for num in nums: for j in range(num, target + 1): dpj += dpj - num

BP VI: for j in range(1, target + 1): for num in nums: if num > j: continue dpj += dpj - num

class Solution {
    public int combinationSum4(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[][] dp = new int[target+1][n+1];
        //dp[0][...] = 0;
        // dp[..][0] = 1;
        
        for(int i = 0; i<=n; i++)
        {
            dp[0][i] = 1;
        }
        
        for(int i = 1; i<= target; i++)
        {
            for(int j = 1; j<= n; j++)
            {
                if(i- nums[j-1] >=0)
                {
                    // 注意这里最后是dp[i- nums[j-1]][n]
                    dp[i][j] = dp[i][j-1] + dp[i- nums[j-1]][n];
                }
                else
                {
                    dp[i][j] = dp[i][j-1];
                }
                
            }
        }
          return dp[target][n]; 
         
    }
}

Version 2: Top down dfs+ memorization search (similar as other combination sum)

class Solution {

    public int combinationSum4(int[] nums, int target) {
        int result = 0;
        Arrays.sort(nums);
        Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
        result = dfs(target, nums, 0, memo);
        return result;
    }
    
    public int dfs(int count, int[] nums, int startIndex, Map<Integer, Integer> memo)
    {
        if(memo.containsKey(count))
        {
            return memo.get(count);
        }
        
        if(count == 0)
        {
            return 1;
        }
        
        if(count < 0)
        {
            return 0;
        }
        
        if(startIndex == nums.length)
        {
            return 0;
        }
        
        int result = 0;
        for(int i = startIndex; i< nums.length; i++)
        {
            if(nums[i] > count) continue;
            result += dfs(count-nums[i], nums, startIndex, memo);
        }
        
        memo.put(count, result);
        return result;
    }
}