Question

Formatted question description: https://leetcode.ca/all/377.html

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

 */

Algorithm

One-dimensional array dp, where dp[i] represents the number of solutions whose target number is i, and then traverses from 1 to target.

For each number i, traverse the nums array, if i>=x

int[] dp = new int[target + 1];

Follow up

If there is negative numbers allowed, there could be infinite possibilities.

  • e.g. target = 1, there is [-1, 1] in nums, then the possible ways could be -1+1+1, -1-1+1+1+1

If allowing negative numbers, there can’t be any combiantion of neigatie numers + any combiantion of positive numbers == 0.

Code

Java

  • 
    public class Combination_Sum_IV {
    
        class Solution {
            public int combinationSum4(int[] nums, int target) {
    
                // dp[i] meaning for value i, how many combination count
                int[] dp = new int[target + 1];
                dp[0] = 1;
                for (int targetValue = 1; targetValue <= target; targetValue++) {
    
                    for (int i = 0; i < nums.length; i++) {
    
                        if (nums[i] <= targetValue) {
                            // @note: not dp[targetValue]=dp[targetValue-a]+dp[a]
                            //          becasue both will be added in below line for dp[a] and dp[targetValue-a]
                            dp[targetValue] += dp[targetValue - nums[i]];
                        }
                    }
                }
    
                return dp[target];
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/combination-sum-iv/
    // Time: O(NT)
    // Space: O(T)
    class Solution {
        unordered_map<int, int> m { {0, 1} };
        int dp(vector<int>& nums, int target) {
            if (m.count(target)) return m[target];
            int cnt = 0;
            for (int n : nums) {
                if (n > target) break;
                cnt += dp(nums, target - n);
            }
            return m[target] = cnt;
        }
    public:
        int combinationSum4(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
            return dp(nums, target);
        }
    };
    
  • class Solution(object):
      def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target + 1)
        dp[0] = 1
    
        for i in range(1, target + 1):
          for j in range(1, len(nums) + 1):
            if i - nums[j - 1] >= 0:
              dp[i] += dp[i - nums[j - 1]]
        return dp[-1]
    
    

All Problems

All Solutions