外包网易测试_ecshop源码下载_百度输入法下载_提高基层治理效能

思路

1. dp数组定义：总和为j 共有dp[j]种组合
2. 递推公式：

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

3. dp数组初始化：

   dp[0] = 1

4. 遍历顺序：求排列问题，先背包后物品
5. 时间复杂度：     

代码

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned long long> dp(target + 1, 0);dp[0] = 1;for (int j = 0; j <= target; j++) {for (int i = 0; i < nums.size(); i++) {if (j >= nums[i]) {dp[j] += dp[j - nums[i]];}}}return dp[target];}
};