AlgoPressAppearance
0040-组合总和II
https://leetcode.cn/problems/combination-sum-ii
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
思路
回溯法，数字不能重复使用，只能使用一次，定义 begin 变量 重复使用 used 最后集合不能重复
参考代码
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private bool[] used ;
private int back;
private List<int> CopyList(List<int> list){
List<int> newList = new List<int>();
for(int i=0; i<list.Count; i++){
newList.Add(list[i]);
}
return newList;
}
private void Print(List<int> list){
for(int i=0; i<list.Count; i++){
Console.Write("{0} ",list[i]);
}
Console.WriteLine();
}
private void dfs(int[] candidates, int target, int begin, List<int> list){
if(target < 0){
return ;
}
if(target == 0){
//输出结果
result.Add(CopyList(list));
return;
}
for(int i=begin; i<candidates.Length; i++){
if(!used[i] && candidates[i] != back){
list.Add(candidates[i]);
used[i] = true;
dfs(candidates, target - candidates[i], i+1,list);
back = list[list.Count-1];
list.RemoveAt(list.Count - 1);
used[i] = false;
}
}
}
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
List<int> list = new List<int>();
Array.Sort(candidates);
used = new bool[candidates.Length];
dfs(candidates,target,0,list);
return result;
}
}
参考代码2：不需要 used 数组
需要重新思考下什么时候使用 used 什么时候不用
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private int back;
private List<int> CopyList(List<int> list){
List<int> newList = new List<int>();
for(int i=0; i<list.Count; i++){
newList.Add(list[i]);
}
return newList;
}
private void Print(List<int> list){
for(int i=0; i<list.Count; i++){
Console.Write("{0} ",list[i]);
}
Console.WriteLine();
}
private void dfs(int[] candidates, int target, int begin, List<int> list){
if(target < 0){
return ;
}
if(target == 0){
//输出结果
result.Add(CopyList(list));
return;
}
for(int i=begin; i<candidates.Length; i++){
if( candidates[i] != back){
list.Add(candidates[i]);
dfs(candidates, target - candidates[i], i+1,list);
back = list[list.Count-1];
list.RemoveAt(list.Count - 1);
}
}
}
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
List<int> list = new List<int>();
Array.Sort(candidates);
dfs(candidates,target,0,list);
return result;
}
}
复习:20220512 去重逻辑
- 因为每个数字只用一次，所以先要在每次 dfs 的时候 begin
- 要去重，比如求和 = 8, 数据 1 2 1 5 ， 每个数字只用一次会有两个结果 , 1 2 5 和 2 1 5 所以我们首先要排序变成 1,1,2,5 然后在递归的时候，第二个1不要重复计算。 我们不能使用 candidate[i] = candidate[-1] 的时候就停止处理，因为比如 1,1 后面有个 6 也需要输出。
所以去重，只能是上次参与计算过的数字， 所以我们需要从 list 中取出一个，刚刚要回溯的数字，如果他刚被回溯掉，也就是从list中删除，那我们就没有必要把它再加进去重新运算。
因为在回溯的时候，设置一个 back 的变量，在再次进入 dfs 的时候，检查是否与这个回溯的值相同，如果相同则跳过。
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
int back = -1;
private void dfs(int[] candidates,int begin, int target, List<int> list){
if(target < 0){
return;
}
if(target == 0){ //满足条件输出
result.Add(new List<int>(list));
return;
}
for(int i=begin; i<candidates.Length; i++){
if(i>0 && candidates[i] == back){
continue;
}
list.Add(candidates[i]);
dfs(candidates,i+1,target - candidates[i],list);
back = list[list.Count-1];
list.RemoveAt(list.Count-1);
}
}
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
List<int> list = new List<int>();
dfs(candidates,0,target,list);
return result;
}
}