深度优先搜索实现回溯算法

本文主要是介绍深度优先搜索实现回溯算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

回溯算法用于搜索一个问题的所有解，通过深度优先遍历的思想实现。回溯算法本质上是一种遍历算法，它可以搜索到解决问题的所有方案，时间复杂度很高。
搜索的方法就是按顺序枚举出每一种可能出现的情况，已经选择了的在当前的这一次搜索中就不能出现，这样就能实现不丢不重。

如题：要找出所有不重复的组合，一个数可以使用若干次，这就要用到回溯法把所有可能的搜索出来，使用深度优先搜索+递归的思想，找到底了再回去。【2,2，3】【3,2,2】其实是一种所以在搜索的时候一旦前面的搜索完毕了后面在搜索的时候就不能再考虑前面的数，这就要使用一个循环，每次循环开始的位置都要变化。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        int end = candidates.length;
        if(end == 0){
            return res;
        }
        allCom(0,end,candidates,target,res,path);
        return res;
    }
    public void allCom(int begin,int end,int[] candidates, int target,List<List<Integer>> res,Deque<Integer> path){
        if(target==0){
            res.add(new ArrayList(path));
            return;
        }
        if(target<0){
            return;
        }
        for(int i = begin;i<end;i++){
            path.addLast(candidates[i]);
            allCom(i,end,candidates,target-candidates[i],res,path);
            path.removeLast();
        }
    }
}

如上解法是搜索得非常彻底，但是有的地方没有必要一直进行重复累赘的操作，这就可以用到剪枝的思想，排序是剪枝的前提，一旦这轮的某个数导致target为负数了，那么这一轮搜索到此结束；这个时候的出口就只有一个了。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        getAll(0,len,candidates,target,res,path);
        return res;
    }

    public void getAll(int begin,int len,int[] candidates,int target,List<List<Integer>> res,Deque<Integer> path){
        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = begin;i<len;i++){
            if(target - candidates[i] < 0){
                break;
            }
            path.addLast(candidates[i]);
            getAll(i,len,candidates,target-candidates[i],res,path);
            path.removeLast();
        }
    }
}

这篇关于深度优先搜索实现回溯算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！