377. 组合总和 Ⅳ

Problem: 377. 组合总和 Ⅳ

思路

讲述看到这一题的思路

解题方法

纯纯的背:

求装满背包的方法 dp[j] += dp[j - nums[i]]。

注意遍历背包和遍历物品的顺序。

有下面两种：

排列问题：先背包再物品，注意内层循环判断背包大于物品

组合问题：先物品再背包，注意遍历背包要倒序

本题是排列问题。

Code

[]

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //求排列，先背包再物品，可以取多个，完全背包，都是正序遍历
        vector<int> dp(target+1,0);
        dp[0] = 1;
        for(int j = 1;j<=target;j++){
            for(int i = 0; i < nums.size(); i++){
                if(j >= nums[i] && dp[j] < INT32_MAX-dp[j-nums[i]]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
};