江苏龙网

  1. 主页 > 生活百科 > >

回溯算法的题目，这样做，秒杀( 四 )

回溯算法


39. 组合总和 难度中等

回溯算法的题目，这样做，秒杀

文章插图
 
这个题目跟之前的没有什么太大的区别，只是需要注意一个点：每个数字可以被无限制重复被选取，我们要做的就是在递归的时候，i的下标不是从i+1开始，而是从i开始 。
    backTrace(i,candidates,target-candidates[i], temp);我们看看完整代码 。
    List<List<Integer>> list = new ArrayList<>();    public List<List<Integer>> combinationSum(int[] candidates, int target) {        if(candidates.length == 0 || target < 0){            return list;        }        List<Integer> temp = new ArrayList<>();        backTrace(0,candidates,target,temp);        return list;    }    public void backTrace(int start, int[] candidates, int target, List<Integer> temp){        //递归的终止条件        if (target < 0) {            return;        }        if(target == 0){            list.add(new ArrayList<>(temp));        }         for(int i = start; i < candidates.length; i++){            temp.add(candidates[i]);            backTrace(i,candidates,target-candidates[i], temp);            temp.remove(temp.size()-1);        }    }就是这么简单！！！
那么，再来一个组合问题 。
40. 组合总和 II 难度中等
回溯算法的题目，这样做，秒杀

文章插图
 
你一看题目是不是就发现，差不多啊，确实，这里只是每个数字只能用一次，同时也是不能包含重复的组合，所以，用上面的去重方法解决咯 。话不多说，上代码 。
    List<List<Integer>> lists = new LinkedList<>();    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        if(candidates.length == 0 || target < 0){            return lists;        }        Arrays.sort(candidates);        List<Integer> list = new LinkedList<>();        backTrace(candidates,target,list, 0);        return lists;    }    public void backTrace(int[] candidates, int target, List<Integer> list, int start){        if(target == 0){            lists.add(new ArrayList(list));        }                for(int i = start; i < candidates.length; i++){            if(target < 0){                break;            }            //剪枝：保证同一层中只有1个相同的元素，不同层可以有重复元素            if(i > start && candidates[i] == candidates[i-1]){                continue;            }            list.add(candidates[i]);            backTrace(candidates,target-candidates[i],list,i+1);            list.remove(list.size()-1);        }    }


推荐阅读


上一篇：什么叫淘宝客pid 淘宝客pid在哪里

下一篇：淘宝老客户优惠券如何设置 淘宝怎么设置淘客优惠券