40. Combination Sum II

,

Backtracking + DFS

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
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 00
        // 01
        // 10
        // 11

        List<List<Integer>> resultList = new ArrayList<>();

        Arrays.sort(candidates);
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, candidates, 0, false, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int[] candidates, int i, boolean chosenPre, int sum, int target) {
        if (sum > target) {
            return;
        }
        if (i == candidates.length) {
            if (sum == target) {
                resultList.add(new ArrayList<>(numList));
            }
            return;
        }

        if (i > 0 && candidates[i] == candidates[i - 1] && chosenPre) {
            // 减去重复的选择：10
        } else {
            // not choose
            dfs(resultList, numList, candidates, i + 1, false, sum, target);
        }

        // choose
        numList.add(candidates[i]);
        dfs(resultList, numList, candidates, i + 1, true, sum + candidates[i], target);
        numList.remove(numList.size() - 1);
    }
}

Backtracking + DFS

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
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 00
        // 01
        // 10
        // 11

        List<List<Integer>> resultList = new ArrayList<>();

        Arrays.sort(candidates);
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, candidates, 0, false, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int[] candidates, int i, boolean chosenPre, int sum, int target) {
        if (sum > target) {
            return;
        }
        if (i == candidates.length) {
            if (sum == target) {
                resultList.add(new ArrayList<>(numList));
            }
            return;
        }

        // not choose
        dfs(resultList, numList, candidates, i + 1, false, sum, target);

        if (i > 0 && candidates[i] == candidates[i - 1] && !chosenPre) {
            // 减去重复的选择：01
            return;
        }

        // choose
        numList.add(candidates[i]);
        dfs(resultList, numList, candidates, i + 1, true, sum + candidates[i], target);
        numList.remove(numList.size() - 1);
    }
}

Backtracking + DFS

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 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 去重则需要排序

        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, candidates, 0, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int[] candidates, int startIndex, int sum, int targetSum) {
        if (sum == targetSum) {
            resultList.add(new ArrayList<>(numList));
            return; // 提前返回，不加也能 AC, 因为题目保证了 candidates[i] >= 1
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > targetSum) {
                // 后面的元素只可能大于等于 candidates[i], 所以此处使用 break 彻底剪枝
                break;
            }
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                // 同层去重
                continue;
            }

            numList.add(candidates[i]);
            dfs(resultList, numList, candidates, i + 1, sum + candidates[i], targetSum); // 注意元素不能重复使用，所以传入的参数为 i + 1
            numList.remove(numList.size() - 1);
        }
    }
}

References

40. Combination Sum II
剑指 Offer II 082. 含有重复元素集合的组合