关于回溯算法

算法"/>

关于回溯算法

回溯算法

回溯是蛮力法的一种，回溯只是更有组织的穷举每一种可能，可以通过剪枝操作来提高效率。有递归的地方就会有回溯，第j次递归结束退回至第j-1次递归的过程就可以看作是回溯的过程。其解空间可以用一颗树来表示称为解空间树。

解空间树是回溯法中比较重要的概念，解空间树一般分为两种：一种是子集树（从的集合中找出满足某种性质的子集时），另一种是排列树（从的集合中找出满足某种性质）。一般情况下这两种可以互相转化，有的时候会显得比较抽象，在这里就不做区分。直在回溯算法中，我们通常使用一个路径（path）来记录每一次的决策结果，使用一个结果集（ans）来存储所有满足条件的解。算法的框架如下：

class Main{//ans存放所有满足条件的结果List<List<E>> ans=new ArrayList<List<E>>();//path存放的是每一次决策的结果List<E> path=new ArrayList<>();public void backtracking(参数列表,int index){//递归出口if(满足条件){ans.add(new ArrayList<>(path));return;}for(int i=index;i<n;i++){//这里的n一般时给定集合的大小path.add(当前决策);//决策，满足条件，添加到本次的结果中backtracking(参数列表,下一层递归的起始位置，i或i+1或其他);path.remove(path.size()-1);//回溯，撤销本次决策}}
}

其中，"满足条件"指的是问题的特定要求，可以根据具体问题进行定义。"当前决策"指的是在当前层次的递归中做出的选择，可以根据问题的不同而有所变化。"下一层递归的起始位置"指的是在递归的下一层中，从哪个位置开始继续递归，也可以根据问题进行调整。

回溯算法的关键点在于递归的出口和决策的撤销。递归的出口是确定何时达到了满足条件的状态，这时将当前的路径加入结果集。决策的撤销是在递归完成后，将当前的决策结果移除，以便进行下一次尝试。

递归的出口已经确实是i还是i+1是非常重要的。假设在给定的集合s中选择满足条件的n个数，这种情况下递归的出口就是path.size()==n，若集合s的元素是可以重复选择的那么一定是i，不可以重复则就是i+1。

在确定递归出口的时候，有时候需要设置一个全局变量，例如在非降序的集合s中选择若干个元素（可以重复选择），使得和为target，那么这时就需要一个全局变量sum来存储已经选择了的元素的和，path就是选择了的元素的集合。此时不仅pah需要回溯，sum也需要回溯。伪代码如下：

class Main{//ans存放所有满足条件的结果List<List<E>> ans=new ArrayList<List<E>>();//path存放的是每一次决策的结果List<E> path=new ArrayList<>();int sum=0;//记录决策之和public void backtracking(int[] s,int index,int target){//递归出口if(sum>target){/return;}if(sum==target){ans.add(new ArrayList<>(path));return;}for(int i=index;i<s.length;i++){path.add(s[i]);//满足条件，添加到本次的结果中sum+=s[i];backtracking(s,i,target);//可以重复选择//回溯，撤销这次决策sum-=s[i];path.remove(path.size()-1);}}
}

使用java语言时，可以将非引用的数据类型当作参数而不用声明全局变量，例如在上述代码中sum就不用声明为全局变量，而是出现在backtracking的参数中backtracking(sum+s[i],s,i,target)或者backtracking(s,i,target-s[i])，也就是不需要写sum+=以及sum-=至于为什么，仔细想想就应该能够明白。

接下来我会持续更新leetcode上边有关回溯算法的题目，可以结合题目来理解回溯算法，理解解空间树。