跳到主要内容

Combination Sum IV

问题描述​

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
  • Every element is unique
  • 0 <= target <= 1000

分析​

本题与Coin Change II很类似，不过求的是排列数而不是组合数。

求排列数的时候，必须是外层for遍历背包，内层for循环遍历物品。

代码​

// Combination Sum IV
// Time Complexity: O(n*target), Space Complexity: O(target)
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long int> dp(target + 1);
        dp[0] = 1; // base case

        for (int j = 0; j <= target; j++) {
            for(int w : nums) {
                if (j >=w) {
                    dp[j] += dp[j-w];
                }
            }
        }
        return dp[target];
    }
};