LC.P39[组合总和]

方法一：朴素回溯

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 {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        dfs(0, target);
        return ans;
    }

    private void dfs(int i, int target) {
        if (i == candidates.length) return;
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不选
        dfs(i + 1, target);
        // 选
        if (target - candidates[i] >= 0) {
            path.add(candidates[i]);
            dfs(i, target - candidates[i]);
            path.remove(path.size() - 1);
        }
    }
}

方法二：回溯+剪枝

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
class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        Arrays.sort(candidates);
        dfs(0, target);
        return ans;
    }

    private void dfs(int i, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (i == candidates.length || target < candidates[i]) {
            return;
        }
        // 不选
        dfs(i + 1, target);

        // 选
        path.add(candidates[i]);
        dfs(i, target - candidates[i]);
        path.remove(path.size() - 1);
    }
}

方法三：回溯+剪枝

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 {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        Arrays.sort(candidates);
        dfs(0, target);
        return ans;
    }

    private void dfs(int start, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 剪枝一：从 start 开始遍历，避免产生重复解
        for (int i = start; i < candidates.length; ++i) {
            // 剪枝二：若当前子集和已超过 target，则直接结束循环(因为数组已排序，后面的元素更大，一定会超过 target)
            if (target - candidates[i] < 0) break;
            path.add(candidates[i]);
            dfs(i, target - candidates[i]);
            path.remove(path.size() - 1);
        }
    }
}