377号组合数问题
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
河水洗回忆
2018-02-28
老师您好！377号问题是求从数组中挑选一些数组成特定和的组合数，我不理解为什么把完全背包问题中的目标数放在外循环，数组中数放在内循环求出的就是包含重复的结果，可以给我解释一下么？
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int n=nums.size();
if(n==0)
return 0;
vector<int> memo(target+1,0);
memo[0]=1;
for(int i=1;i<=target;i++)
{
for(int j=0;j<n;j++)
{
if(nums[j]<=i)
memo[i]=memo[i]+memo[i-nums[j]];
}
}
return memo[target];
}
};2回答
-
如果数组中的数字放在外循环，相当于：已知用nums[0...i]这些数字凑成[0...target]的方法数，现在需要新考虑一个数字nums[i+1]，现在，凑成[0...target]的方法有多少？此时，新考虑的这个nums[i+1]摆在哪里变成了问题。以凑成j为例，由于之前凑成j的方法完全没有用这个nums[i+1]，所以nums[i+1]可以摆放在原先凑成j的所有方法的所有数字之间！（这还不考虑需要多个nums[i+1]的情况）。所以，所以，仅仅记住原先用nums[0...i]这些数字凑成j的方法数量是不够的，还需要具体是怎么凑出来的，才能找到摆放新的nums[i+1]的所有方法。
但是把目标数放在外循环，相当于每次需要考虑：用所有的nums数字凑成[0...j]的方法数已经知道了，现在要凑成j+1，多了几种方法？这时，用所有的nums凑成[0...j]的数量中，已经包含了不同顺序的结果，我们只需要考虑，在现有的所有凑成的方法后面，添加nums[0], nums[1], nums[2]，... 能不能凑成j+1就好了。
这么说可能还是比较抽象。如果觉得自己理解的还不够透彻，我建议你用377号题目的例子：nums = [1, 2, 3]，target = 4，走一遍上面的程序。i从1到4；j从0到2，一共循环才执行12次。每次更新memo[i]的时候，如果memo[i]变大了的话，都自己写出当前的memo[i]所记录的凑成数字i的方法数都是那几种（一共才7种），一定可以帮助你更深刻的理解这个问题。不要嫌麻烦！跟踪经典算法实现中的变量是如何变化的，想明白为什么会这么变化，和自己哪里理解的不一样，或者自己之前的理解漏掉了什么，是深入理解算法的非常有效的方法：）
如果在这个基础上，能够自己尝试换个方法编写，就更好了。比如自己实际思考一下，如果两层循环的顺序变了，在实现逻辑上到底有什么差别？有什么改变？多做这样的思考和实验，代码水平想不提高都难：）
加油！
052022-10-21 -
ShiveryMoon
2018-03-03
我正好也想问这个问题来着，内外层循环反过来居然就能从求组合变成求排列，我都傻了
00
相似问题