377-组合总和IV

LeetCode 377. Combination Sum IV

LeetCode-377

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.

method

要求排列数，用回溯会超时，考虑用完全背包，target是背包容量，数组元素是物品，因为是求几种装法，所以递推公式是

dp[j] += dp[j - nums[i]]

求排列数，所以要先遍历背包，再遍历物品

题目给定结果不会越界，但是在计算过程中有些dp值会越界，所以这些dp值肯定不会是结果，就不用考虑了

int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1);
    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];
}