LeetCode39- 组合总和

🔗:参考的题解:LeetCode39- 组合总和

class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path=new ArrayList<>();
        List<List<Integer>> paths=new ArrayList<>();
        Arrays.sort(candidates);//使用排序有利于剪枝
        dfs(candidates,0,paths,path,target);
        List<List<Integer>> res = new ArrayList(paths);
        return res;
    }
    public void dfs(int[] candidates , int begin, List<List<Integer>> paths ,List<Integer> path ,int num){
        if(num==0&&!path.isEmpty()){
            paths.add(new ArrayList<>(path));//这里必须使用深度复制
            return;
        }
		// i设置为begin起到了去重的作用,i=0的时候是搜索所有的路径
		//i=1的时候不会再次去搜索candidate[0]了,因为i=0的时候搜索过了,i=1就是从1开始搜索了!
		//i=1的搜索结果包含了i=0的搜索结果.
        for( int i = begin ; i<candidates.length;++i){
            int next_num = num-candidates[i];
            if(next_num<0){//剪枝的前提是数组有序!
                break;//这里直接break,continue会慢一些
            }
            path.add(candidates[i]);
            dfs(candidates,i,paths,path, next_num);
            if (!path.isEmpty()) {// remove Last element挪走最后一个元素!
                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
31
32
33