题目描述
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
样例
nums = [1, 2, 3]
target = 4
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶
- 如果给定的数组中含有负数会怎么样?
- 问题会产生什么变化?
- 我们需要在题目中添加什么限制来允许负数的出现?
算法
(动态规划) $O(n \cdot target)$
- 设 $f(i)$ 表示组成和为 $i$ 的方案数。
- 初始时,$f(0) = 1$ 其余为 0。
- 转移时,先枚举 $i$ 然后枚举每个数字 $nums[j]$,如果 $i \ge nums[j]$,令 $f(i) = f(i) + f(i - nums[j])$。
- 最终答案为 $f(target)$。
- 注意此题和完全背包的区别,背包问题的状态表示是 $f(i, j)$ 表示前 $i$ 个物体,组成的重量为 $j$,经过优化变成了一维。如果此题用完全背包解答,则会将顺序不同的序列算作相同的组合。
注意
- 此题在求解过程中整数会出现溢出,但由于答案在
32
位整数范围内,所以我们只需要在计算过程中模INT_MAX
即可避免溢出)
时间复杂度
- 状态数为 $target$ 个,每次转移需要 $n$ 次循环,故时间复杂度为 $O(n \cdot target)$。
空间复杂度
- 空间和状态数相等,为 $O(target)$。
进阶
- 如果数组中存在负数,则有可能有无穷多个答案。
- 可以添加负数个数的限制。
C++ 代码
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
const int MOD = INT_MAX;
int n = nums.size();
vector<unsigned> f(target + 1, 0);
f[0] = 1;
for (int i = 1; i <= target; i++)
for (int j = 0; j < n; j++)
if (i >= nums[j])
f[i] = (f[i] + f[i - nums[j]]) % MOD;
return f[target];
}
};
请问这题目如果用搜索算法来做,要怎么优化时间呢?谢谢!
可以按顺序从小到大枚举,如果无法满足 target 可以提前剪枝。但这样需要注意最后答案统计的是无序的情况,变为有序需要使用组合数学,对每种情况乘上各数字出现次数的阶乘
感谢您的回复。我想到了另一种解决思路,在dfs的时候存储
[target] -> 组合情况
。比如
2-> [1, 1], [2]
,表示 target = 2 时有 [1, 1], [2] 两种组合,在以后dfs时遇见 target 为 2 时可以直接使用。当然这题不需要返回具体的结果,直接存组合数就可以。
再次感谢您的帮助!
记忆化搜索就是动态规划,dict就是 f 数组
请问记忆化搜索就是动态规划是一样的吗?
思想是一样的,只是两种不同的实现方式。
在不确定转移顺序(保证转移没有环)的情况下,可以采用记忆化搜索
在确定转移顺序且需要注重效率的情况下,可以采用递推
受教了
加入负数有点像图里找最短路出现负环了。。
大佬,为什么
f[0] = 1
吖?这是初始值呀,组成 0 的方式只有 1 种
我也有类似的困惑,这个题dp递推式与完全背包相同,但完全背包问题可以交换两层循环的顺序,为什么这个题中两层循环的顺序却是不能交换的?(交换后就是LC518的答案了)
仔细想一下和完全背包的异同
明白了,完全背包如果交换两层循环顺序的话,dp表示含义也会变化,交换后不能用01背包的方式来考虑了。
为什么完全背包会不行呢 还是有点不理解
完全背包就会将顺序不同的组合看作一个,你可以用完全背包实现一下,然后看下区别