377. Combination Sum IV

1. 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.

2. Example

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

3. Constraints

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

4. Solutions

Dynamic Programming

m = nums.size(), n = target
Time complexity: O(mn)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int combinationSum4(const vector<int> &nums, int target) {
        vector<uint64_t> count(target + 1, 0);
        count[0] = 1;
        for (int sum = 1; sum <= target; ++sum) {
            for (int num : nums) {
                if (num <= sum) {
                    count[sum] += count[sum - num];
                }
            }
        }

        return count.back();
    }
};