题目描述
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

解题思想
使用完全背包

代码

/*
    dp[i]：表示装满容量为i的背包有dp[i]种方式
    递推公式：dp[j] += dp[j-nums[i]]
    初始化：dp[i] = 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] += dp[j - nums[i]];
                    }
                }

*/
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++) {
                //C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[j] < INT_MAX - dp[i - num]。
                if (j >= nums[i] && dp[j]<INT_MAX-dp[j-nums[i]])
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
        
    }
};