leetcode 377 中的comb[0] 为什么是1？
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
想不出来叫什么
2018-05-21
老师您好！这是leetcode 377的答案代码：
public int combinationSum4(int[] nums, int target) {
int[] comb = new int[target + 1];
comb[0] = 1;
for (int i = 1; i < comb.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i - nums[j] >= 0) {
comb[i] += comb[i - nums[j]];
}
}
}
return comb[target];
}comb[i] 表示target为i时，可用的组合个数，i = 0时，target为0，那么可用的组合个数不应该是0吗（数组中的元素全部为正整数）？
写回答
1回答
-
对于每一个凑成target的组合，可以理解成是一个集合。如题目中的target=4， nums=[1, 2, 3]的情况，结果为7，即为可以找到7个集合，集合中的数字取自[1, 2, 3]且和为4：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)当target为0时，我们可以一个数字都不选，即取一个空集，则可以满足target=0的条件。空集是一个解，所以为1：）
00
相似问题