39. Combination Sum

,

Backtracking

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        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 i, 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, sum, target);

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

以上从各个数字进行选与不选的角度来驱动搜索。

Backtracking

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, 0, candidates, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int[] candidates, int startIndex, int target) {
        if (sum == target) {
            resultList.add(new ArrayList<>(numList));
            return;
        }
        if (sum > target) {
            // 因为本题 candidates 均为正数，故可以剪枝
            return;
        }

        // 每次从 startIndex 开始搜索是为了防止出现重复的组合，如 candidates = [2, 3, 6, 7], target = 7, 其中 [2, 2, 3] 与 [2, 3, 2] 都能组成 target, 但是实际上他们为同一个组合
        // 即每次搜索时不再使用 startIndex 之前的数字，而可以使用 startIndex 指向的数字，因为单个数字可以重复使用
        for (int i = startIndex; i < candidates.length; i++) {
            numList.add(candidates[i]);
            dfs(resultList, numList, sum + candidates[i], candidates, i, target); // 此处没有推进索引，因为数字可以重复使用
            numList.remove(numList.size() - 1);
        }
    }
}

以上将选择逻辑抽象为多叉树来进行搜索，其中 for 循环在同一层上进行选择，for 循环内部的 dfs 函数调用则为进入树的下一层节点。

Backtracking

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        Arrays.sort(candidates); // 剪枝提速，非必须
        dfs(resultList, numList, 0, candidates, 0, target);
        return resultList;
    }

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

        // 每次从 startIndex 开始搜索是为了防止出现重复的组合，如 candidates = [2, 3, 6, 7], target = 7, 其中 [2, 2, 3] 与 [2, 3, 2] 都能组成 target, 但是实际上他们为同一个组合
        // 即每次搜索时不再使用 startIndex 之前的数字，而可以使用 startIndex 指向的数字，因为单个数字可以重复使用
        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                // 在数组升序的情况下才可执行此剪枝
                break;
            }
            numList.add(candidates[i]);
            dfs(resultList, numList, sum + candidates[i], candidates, i, target); // 此处没有推进索引，因为数字可以重复使用
            numList.remove(numList.size() - 1);
        }
    }
}

Backtracking

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);

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

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

        for (int num : candidates) {
            if (sum + num > target) {
                return;
            }
            // 去除元素顺序不同，但是组合相同的组合，如：[[2,2,3],[2,3,2],[3,2,2],[7]]
            if (!numList.isEmpty() && num < numList.get(numList.size() - 1)) {
                continue;
            }

            numList.add(num);
            dfs(resultList, numList, candidates, sum + num, target);
            numList.remove(numList.size() - 1);
        }
    }
}

References

39. Combination Sum
剑指 Offer II 081. 允许重复选择元素的组合