leetcode-39. 组合总和

原始思路

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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    int total = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(0, candidates, target);
        return result;
    }

    public boolean dfs(int k, int[] candidates, int target){
        if (total == target){
            result.add(new ArrayList<Integer>(tmp));
            return false;
        }

        if ((target - total)< candidates[0] || k >= candidates.length || total > target){
            return false;
        }

        tmp.add(candidates[k]);
        total += candidates[k];
        if(!dfs(k, candidates, target)){
            k++;
        }
        total -= tmp.get(tmp.size() - 1);
        tmp.remove(tmp.size() - 1);
        if(!dfs(k, candidates, target)){
            k++;
        }
        return false;
    }
}

题解思路

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{
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    int total = 0;
    Set<String> set = new HashSet<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(0, candidates, target);
        return result;
    }
    
    public void dfs(int begin, int[] candidates, int target){
        if(target == 0){
            //符合条件，加入数据
            result.add(new ArrayList<Integer>(tmp));
            return;
        }
        for(int i = begin; i < candidates.length; i++){
            // 进行剪枝,前提是数组有序
            if(target - candidates[i] < 0){
                break;
            }
            tmp.add(candidates[i]);
            dfs(i, candidates, target - candidates[i]);
            tmp.remove(tmp.size() - 1);
        }
    }
}