40.组合总和2

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

Solution

答案视角：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
    // 用于存储所有可能的组合结果的列表
    List<List<Integer>> result = new ArrayList<>();
    // 用于存储当前路径的列表
    List<Integer> path = new ArrayList<>();

    // 主要方法，寻找所有可以组成目标值 target 的组合
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 对候选数组进行排序，以便在递归中方便处理重复元素
        Arrays.sort(candidates);
        // 开始深度优先搜索，初始状态为索引 0 和目标值 target
        dfs(candidates, target, 0);
        return result;
    }

    // 深度优先搜索方法
    private void dfs(int[] candidates, int target, int start) {
        // 如果目标值 target 小于 0，结束搜索（剪枝）
        if (target < 0) {
            return;
        }

        // 如果目标值 target 等于 0，找到一个合法组合，将其添加到结果列表中
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 遍历候选数组，从索引 start 开始
        for (int i = start; i < candidates.length; ++i) {
            // 选择当前数字，添加到路径中
            path.add(candidates[i]);
            // 递归调用，继续搜索下一个数字，目标值减少当前数字的值
            dfs(candidates, target - candidates[i], i + 1);
            // 回溯，移除当前数字
            path.remove(path.size() - 1);
            // 关键：递归后去除后续重复数字
            // 跳过所有相同的数字以避免重复结果
            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
                ++i;
            }
        }
    }


}

选择视角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private final ArrayList<List<Integer>> ans=new ArrayList<>();
    private final List<Integer> path=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
          Arrays.sort(candidates);
          dfs(0,target,candidates);
        
          return ans;
    }
    public void dfs(int i,int t,int [] candidates){
           if(t==0){
             ans.add(new ArrayList<>(path));
             return;
           }
           if(t<0||i==candidates.length){
             return ;
           }
          

           path.add(candidates[i]);
           dfs(i+1,t-candidates[i],candidates);
           path.remove(path.size()-1);

           while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
                i++;
            }

           dfs(i+1,t,candidates);


    }
}