回溯算法练习

写的力扣的算法题目，一口气把所有组合总和的题做了，有一道还击败了99%的人，也可能是运气好吧。

39.组合总和

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> tmp_res = new ArrayList<>();
        back_track(candidates,target,results,tmp_res,0);
        return results;
    }
    public void back_track(int[] candidates, int target, List<List<Integer>> results, List<Integer> tmp_res,int num){//num是索引
        if(target < 0)return;
        if(target == 0){
            //results.add(tmp_res);//浅拷贝
            results.add(new ArrayList(tmp_res));
            return;
        }
        for(int i = num;i < candidates.length; i++){
            tmp_res.add(candidates[i]);
            back_track(candidates,target-candidates[i],results,tmp_res,i);
            tmp_res.remove(tmp_res.size() - 1);//清零
        }
    }
}

40.组合总和II

这道题的重点在于如何去重。 一种方案是Set，但是由于Set是红黑树底层，其效率过低。 一种巧妙的方案是：
自愧不如，我去重的方法是。。。。。

return ans.stream().distinct().collect(Collectors.toList());

哭辽。按照大佬的思路，back_track里面正在循环的元素与上一个元素相等的时候，直接continue。效率和内存都大大提升。

哦，还有一个存留问题，

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //int[] candidates = {2,5,2,1,2};
        //target = 5;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp_ans = new ArrayList<>();
        Arrays.sort(candidates);
        System.out.println(candidates.length);
        back_track(candidates,target,ans,tmp_ans,0);
        return ans;//.stream().distinct().collect(Collectors.toList());
    }
    public void back_track(int[] candidates, int target, List<List<Integer>> ans, List<Integer> tmp_ans, int num){
        if(target<0)return;
        if(target == 0){
            ans.add(new ArrayList(tmp_ans));
            return;
        }
        for(int i=num;i < candidates.length; i++){
            if(i>num&&candidates[i] == candidates[i-1])continue;
            if(target<0)break;//根据都是正整数的条件加速
            tmp_ans.add(candidates[i]);
            back_track(candidates,target - candidates[i],ans,tmp_ans,i+1);
            tmp_ans.remove(tmp_ans.size() - 1);
        }
    }
}

216 组合总数III

class Solution {
    public List<List<Integer>> combinationSum3(int k, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp_ans = new ArrayList<>();
        int[] candidates = {1,2,3,4,5,6,7,8,9};
        System.out.println(candidates.length);
        back_track(candidates,target,ans,tmp_ans,k,0);
        return ans;//.stream().distinct().collect(Collectors.toList());
    }
    public void back_track(int[] candidates, int target, List<List<Integer>> ans, List<Integer> tmp_ans, int flag,int num){
        if(target<0)return;
        if(target == 0 && flag ==0){
            ans.add(new ArrayList(tmp_ans));
            return;
        }
        for(int i=num;i < candidates.length; i++){
            if(i>num&&candidates[i] == candidates[i-1])continue;
            if(target<0||flag<0)break;//根据都是正整数的条件加速
            tmp_ans.add(candidates[i]);
            back_track(candidates,target - candidates[i],ans,tmp_ans,flag - 1,i+1);
            tmp_ans.remove(tmp_ans.size() - 1);
        }
    }
}

作者：guo-guo-tm
链接：https://leetcode-cn.com/problems/combination-sum-iii/solution/zai-zu-he-zong-he-ii-de-ji-chu-shang-jia-liao-yi-g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Donate