Skip to content

Combination Sum IV⚓︎

Link

Description⚓︎

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:
1
2
3
4
5
6
7
8
9
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

Solution⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i >= nums[j] && dp[i] < INT_MAX - dp[i - nums[j]]) 
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

Another way of writing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i >= nums[j]) 
                    dp[i] = (0LL + dp[i] + dp[i - nums[j]]) % INT_MAX;
            }
        }
        return dp[target];
    }
};