Problem description:

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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?

Solution:
Think about the recurrence relation first. How does the # of combinations of the target related to the # of combinations of numbers that are smaller than the target?

So we know that target is the sum of numbers in the array. Imagine we only need one more number to reach target, this number can be any one in the array, right? So the # of combinations of target, comb[target] = sum(comb[target - nums[i]]), where 0 <= i < nums.length, and target >= nums[i].

In the example given, we can actually find the # of combinations of 4 with the # of combinations of 3(4 - 1), 2(4- 2) and 1(4 - 3). As a result, comb[4] = comb[4-1] + comb[4-2] + comb[4-3] = comb[3] + comb[2] + comb[1].

In the code, I use a dp array to represent the combination array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        sort(nums.begin(), nums.end());
          
        for (int i = 1; i <= target; ++i) {
            for (auto n : nums) {
                if (i < n) break; //can not use n as i's candidate
                dp[i] += dp[i - n];
            }
        }
        return dp.back();
    }
};