39. 组合总和
一句话套路组合回溯,递归传 i 允许重复选
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释: 2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选, 7 = 7 。 仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1 输出: []
提示:
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
思路
时间
O(2^target/min)空间
O(target/min)思路
组合型回溯 + 「同一个元素可重复选」-> 递归时传 i 而不是 i+1。
排序后可以在 sum > target 时直接 break(后续更大),这是最有价值的剪枝。
对比 Q40(每个元素只能用一次且含重复值):传 i+1,并加if (i > start && candidates[i] == candidates[i-1]) continue; 去重。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0039 {
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 为了 break 剪枝
vector<vector<int>> ans;
vector<int> path;
dfs(candidates, 0, target, 0, path, ans);
return ans;
}
private:
static void dfs(const vector<int>& c, int start, int target, int sum, vector<int>& path,
vector<vector<int>>& ans) {
if (sum == target) {
ans.push_back(path);
return;
}
for (int i = start; i < (int)c.size(); ++i) {
if (sum + c[i] > target) break; // 已排序 -> 后面只会更大,整层剪掉
path.push_back(c[i]);
dfs(c, i, target, sum + c[i], path, ans); // 注意是 i,不是 i+1
path.pop_back();
}
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0039::Solution s;
vector<int> a{2, 3, 6, 7};
CHECK_EQ(s.combinationSum(a, 7), vector<vector<int>>({{2, 2, 3}, {7}}));
vector<int> b{2, 3, 5};
CHECK_EQ(s.combinationSum(b, 8), vector<vector<int>>({{2, 2, 2, 2}, {2, 3, 3}, {3, 5}}));
vector<int> c{2};
CHECK_EQ(s.combinationSum(c, 1), vector<vector<int>>{}); // 凑不出来