Leetcode 40. 组合总和 II
这题是LCR 083. 全排列题目上的进阶变形,需要在原来的深度优先搜索上进行剪枝来进行优化,满足题目要求。主要思路就是:搜索每一种情况,并且通过剪枝优化来去掉重复的情况和不满足的情况。以下是我的代码:
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans= []
candidates.sort()
def dfs(start: int, s: int, path: List[int]):
if s == target:
ans.append(list(path))
return
if s > target:
return
for i in range(start, len(candidates)):
if candidates[i] > target:
break
if i > start and candidates[i] == candidates[i - 1]:
continue
path.append(candidates[i])
dfs(i + 1, s + candidates[i], path)
path.pop()
dfs(0, 0, [])
return ans
C++:
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;
// 剪纸1:排序
sort(candidates.begin(), candidates.end());
vector<int> path;
vector<bool> vis(candidates.size(), false);
function<void(int, int)> dfs = [&](int start, int sum) {
// 找到一种情况
if (sum == target) {
ans.push_back(path);
return;
}
if (sum > target) return;
for (int i = start; i < candidates.size(); i ++) {
if (candidates[i] > target) {
break;
}
// 这个剪枝很重要,避免重复的子集
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
path.push_back(candidates[i]);
// dfs(start + 1, sum + candidates[i])
dfs(start + 1, sum + candidates[i]);
path.pop_back();
}
};
dfs(0, 0);
return ans;
}
};
接下来讲解一些剪枝的作用:
剪枝1:
如果此时总和已经超过target了,那么就直接返回!!!
剪枝2:
这个剪枝相当重要,并且不易想到。去掉重复的子集!!!!
剪枝3:
和剪枝1大同小异,如果总和超过了就不需要再往下进行搜索了!!!!
剪枝4:
要从i + 1开始,如果不小心写成了 start + 1(这个错误很难发现,亲身体会!!!),那就会多出很多重复的集合(虽然顺序不一样)。
到这里就差不多结束啦!!加油!!
会持续更新!!!