377

377. Combination Sum IV (Medium)

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?

Companies: Amazon, Google, Facebook

Related Topics:
Array, Dynamic Programming

Similar Questions:

• Combination Sum (Medium)
• Ways to Express an Integer as Sum of Powers (Medium)

Solution 1. DP Top-down

// OJ: https://leetcode.com/problems/combination-sum-iv/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(T)
class Solution {
public:
    int combinationSum4(vector<int>& A, int target) {
        sort(begin(A), end(A));
        int N = A.size();
        unordered_map<int, int> m{{0, 1}};
        function<int(int)> dp = [&](int target) {
            if (m.count(target)) return m[target];
            int ans = 0;
            for (int i = 0; i < N && A[i] <= target; ++i) {
                ans += dp(target - A[i]);
            }
            return m[target] = ans;
        };
        return dp(target);
    }
};

Solution 2. DP bottom-up

// OJ: https://leetcode.com/problems/combination-sum-iv/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(T)
class Solution {
public:
    int combinationSum4(vector<int>& A, int target) {
        sort(begin(A), end(A));
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int n : A) {
                if (n > i) break;
                dp[i] += dp[i - n];
            }
        }
        return dp[target];
    }
};