LeetCode: 377. Combined sum IV

Here you are Different An array of integers nums , And a target integer target . Please start from nums Find and return the sum of target The number of element combinations of .

The data of the questions ensure that the answers are in line with 32 Bit integer range .

 

Example 1：

Input ：nums = [1,2,3], target = 4
Output ：7
explain ：
All possible combinations are ：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Please note that , Different sequences are considered as different combinations .
Example 2：

Input ：nums = [9], target = 3
Output ：0
 

Tips ：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums All elements in Different from each other
1 <= target <= 1000

analysis ：

        At first, I used the search method to do , It turned out to be over time . Later I saw that it was necessary to use a dynamic gauge , In fact, it is a very simple problem . for instance , If target = 6,nums = {2, 3, 4}, that dp[6] = dp[4] + dp[3] + dp[2], I.e. composition 6 The combination number of is from 4,3,2 These three numbers are transferred from . The border dp[0] = 1. Just one thing to be aware of is dp[i - nums[j]] < INT_MAX - dp[i], One limitation of taphole .
 

class Solution {
public:
    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(nums[j] <= i && dp[i - nums[j]] < INT_MAX - dp[i])
                    dp[i] += dp[i - nums[j]];
        return dp[target];
    }
};