转 http://www.zhimengzhe.com/bianchengjiaocheng/Javabiancheng/257227.html
1、回溯法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
如果需要求所有的解，则需要对每个状态进行搜索。（函数返回值设为void）如果要求存在一个解，那么找到某个解直接返回即可。（函数返回值设为boolean）
2、算法框架
回溯法主要分为求所有的解求存在一个解，其代码框架如下所示。
核心把握：
结果收集条件（回溯结束条件）继续进入下一层搜索条件搜索上界下界
//求所有解的算法框架 public void backtracting(temp){ if("temp是一个结果"){ //结果收集条件 加入结果集; return; } for(j=start;j<= end;j++){ if("不满足加入条件") continue; temp.add(a); //加入当前元素 backtracting(j+1); //继续进行下一步搜索 temp.remove(a); //回溯的清理工作，把上一步的加入结果删除 } } //求存在解的算法框架 public boolean backtracting(temp){ if("temp是一个结果"){ //结果收集条件 加入结果集; return true; } for(j=start;j<= end;j++){ if("不满足加入条件") continue; temp.add(a); //加入当前元素 if(backtracting(j+1)) return true; //继续进行下一步搜索 temp.remove(a); //回溯的清理工作，把上一步的加入结果删除 return false; } } 3、回溯法解题的一般步骤
（1）针对所给问题，确定问题的解空间： 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。（2）确定结点的扩展搜索规则，搜索的结果一定要包括要求的解。（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索（求存在解的问题会出现剪枝）。4、常见题目示例
77. Combinations
Given two integersnandk, return all possible combinations ofknumbers out of 1 ...n.
For example,
Ifn= 4 andk= 2, a solution is:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
题目：从1----n中选出k个数作为组合，求出所有的组合具体的序列。
思路：回溯法，每次从下界开始遍历，到上界结束。满足size() == k 则加入结果，所有解都求出则结束遍历。也可以用二进制模拟的方法。
public class Solution { List > res = new LinkedList >(); public List > combine(int n, int k) { if(k==0) return res; helper(k,n,1,new LinkedList ()); return res; } public void helper(int k,int n,int start,List out){ if(k<=0) return; if(k == out.size()){ List temp = new LinkedList (out); res.add(temp); return; } for(int i=start;i<=n;i++){ out.add(i); helper(k,n,i+1,out); //因为是组合，元素无关顺序，所以每次从下一步进行搜索 out.remove(out.size()-1); } }}
39. Combination Sum
Given asetof candidate numbers (C)(without duplicates)and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.
Thesamerepeated number may be chosen fromCunlimited number of times.
Note:
All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.
For example, given candidate set[2, 3, 6, 7]and target7,
[ [7], [2, 2, 3]]
题目：求一个set之中【没有相同的元素】，和为target的组合数。
思路：回溯，收集条件即为当前序列的 target == 0，其他和求组合一样。
public class Solution { public List > list = new LinkedList >(); public List > combinationSum(int[] candidates, int target) { if(candidates.length == 0) return list; helper(candidates,target,new LinkedList (),0); return list; } public void helper(int[] candidates,int target,List temp,int start){ //维护一个target代表当前的和，0表示temp元素之和等于target， if(target<0) //为了便于判断收集条件 return; if(target == 0){ list.add(new LinkedList (temp)); return; } for(int i=start;i
40. Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.
Each number inCmay only be usedoncein the combination.
Note:
All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.
For example, given candidate set[10, 1, 2, 7, 6, 1, 5]and target8,
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]
题目：求一个set之中【有相同的元素】，和为target的组合数【组合不能重复】。
思路：在回溯之前的条件判断中加入和前一个元素相比，如果相同就不加入。 nums[i] == nums[i-1] continue;
public class Solution { public List > list = new LinkedList >(); public List > combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); if(candidates.length == 0) return list; helper(candidates,target,new LinkedList (),0); return list; } public void helper(int[] candidates,int target,List temp,int start){ if(target<0) return; if(target == 0){ list.add(new LinkedList (temp)); return; } for(int i=start;i start && candidates[i] == candidates[i-1]) continue; temp.add(candidates[i]); helper(candidates,target-candidates[i],temp,i+1); temp.remove(temp.size()-1); } }}
216. Combination Sum III
Find all possible combinations ofknumbers that add up to a numbern, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input:k= 3,n= 7
Output:
[[1,2,4]]
Example 2:
Input:k= 3,n= 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
题目：在1-----9中找出k个元素使其相加等于n
思路：和前面的题类似，回溯下界1 上界9 ，收集的时候限定条件改为 temp.size() == k && target == 0
public class Solution { List > res = new LinkedList >(); public List > combinationSum3(int k, int n) { if(k == 0){ return res; } hleper(n,k,1,new LinkedList ()); return res; } public void hleper(int sum,int k,int start,List templist){ if(sum < 0) return; if(sum == 0 && templist.size()==k) { List li = new ArrayList (templist); res.add(li); return; } for(int i=start;i<=9;i++){ templist.add(i); hleper(sum-i,k,i+1,templist); templist.remove(templist.size()-1); } }}
46. Permutations
Given a collection ofdistinctnumbers, return all possible permutations.
For example,
[1,2,3]have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
题目：求出0一串不同的数字的全排列。
思路：1、回溯法深搜，每次都从0------end搜索，不过需要有一个标记数组，来记录哪些已经访问过了，回溯的时候加入的元素以及标记都需要清除。
public class Solution { List > res = new LinkedList >(); public List > permute(int[] nums) { if(nums.length == 0) return res; int[] temp = new int[nums.length+1]; helper(nums,new LinkedList (),temp); return res; } public void helper(int[] nums,List out,int[] visited){ if(nums.length == out.size()){ List temp = new LinkedList (out); res.add(temp); return; } for(int i=0;i
47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]have the following unique permutations: [ [1,1,2], [1,2,1], [2,1,1]]
题目：给出含有相同数字的元素，求所有元素的排列。
思路：当nums[i] == nums[i-1] 时候，直接进行下一轮搜索，因为如果进行深搜索的话，得出的结果会和之前的重复。即在if(条件处)限定具体的条件。
public class Solution { public List > list = new LinkedList >(); public List > permuteUnique(int[] nums) { Arrays.sort(nums); if(nums.length == 0) return list; int[] visited = new int[nums.length+1]; helper(nums,new LinkedList (),visited); return list; } public void helper(int[] nums,List temp,int[] visited){ if(temp.size() == nums.length){ list.add(new LinkedList (temp)); return; } for(int i=0;i 0 && nums[i]==nums[i-1]&&visited[i-1]==1) continue; //具体的限定nums[i-1]==nums[i]则进行下一轮搜索，同时引入标记矩阵。 if(visited[i] == 0){ visited[i]=1; temp.add(nums[i]); helper(nums,temp,visited); visited[i]=0; temp.remove(temp.size()-1); } } }}
22. Generate Parentheses
Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, givenn= 3, a solution set is:
[ "((()))", "(()())", "(())()", "()(())", "()()()"]
题目：求出所有有效括号的全排列
思路：针对一个长度为2n的合法排列，第1到2n个位置都满足如下规则：左括号的个数大于等于右括号的个数
设left和right分别为剩余的左右括号数目，则使用递归求解可以分为以下几种情况1、left>0 可以继续加括号2、left=0 and right=0 结果收集3、right>0 还需要满足right>left加入右括号
public class Solution { public List list = new LinkedList (); public List generateParenthesis(int n) { if(n == 0) return list; generate(n,n,"",list); return list; } public void generate(int left,int right,String res,List list){ if(left == 0 && right == 0){ list.add(res); return; } if(left>0){ generate(left-1,right,res+"(",list); } if(right>0 && right>left){ generate(left,right-1,res+")",list); } }} 78. Subsets
Given a set ofdistinctintegers,nums, return all possible subsets.
Note:The solution set must not contain duplicate subsets.
For example,
Ifnums=[1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]
题目：求一个集合的子集，集合中不包含相同元素
思路：1、二进制模拟运算，每一个组合代表一个二进制(1代表取，0代表不取)。2、回溯法，和求组合的方式类似，不过收集条件改为来一个收集一个，即不加任何
收集条件，也可以看成if(true) 收集;
//二进制模拟计算public class Solution { List > res = new LinkedList >(); public List > subsets(int[] nums) { int n = nums.length; int count =1< temp = new LinkedList (); int k=i; for(int j=0;j >1; if(flag==0) temp.add(nums[j]); } res.add(temp); } return res; }}
//回溯法public class Solution { public List > res = new LinkedList >(); public List > subsets(int[] nums) { if(nums.length == 0) return res; helper(new LinkedList (),0,nums); return res; } public void helper(List temp,int start,int[] nums){ res.add(new LinkedList (temp)); for(int i=start;i
90. Subsets II
Given a collection of integers that might contain duplicates,nums, return all possible subsets.
Note:The solution set must not contain duplicate subsets.
For example,
Ifnums=[1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], []]
题目：求含有重复元素的数组的子集合不能包含两个相同的子集合【和数学的集合不同】。
思路：先排序，递归进入下一层的条件 nums[i] != nums[i-1]。
public class Solution { public List > res = new LinkedList >(); public List > subsetsWithDup(int[] nums) { Arrays.sort(nums); if(nums.length == 0) return res; helper(new LinkedList (),0,nums); return res; } public void helper(List temp,int start,int[] nums){ res.add(new LinkedList (temp)); for(int i=start;i start && nums[i]==nums[i-1]) continue; temp.add(nums[i]); helper(temp,i+1,nums); temp.remove(temp.size()-1); } }}
526. Beautiful Arrangement
Suppose you haveNintegers from 1 to N. We define a beautiful arrangement as an array that is constructed by theseNnumbers successfully if one of the following is true for the ithposition (1 ≤ i ≤ N) in this array:
The number at the ithposition is divisible byi.iis divisible by the number at the ithposition.
Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2Output: 2Explanation: The first beautiful arrangement is [1, 2]: Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1). Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2). The second beautiful arrangement is [2, 1]: Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1). Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
题目：这道题给了我们1到N，总共N个正数，然后定义了一种优美排列方式，对于该排列中的所有数，如果数字可以整除下标，或者下标可以整除数字，那么我们就是优美排列，让我们求出所有优美排列的个数。
思路：pos表示下标，排列完成，并记录排列位置，visited是否被访问，使用回溯。在进行下一步的搜索的时候条件
为 pos%i ==0 || i%pos == 0 && visited[i] = 0 没有被访问过并且可以被收集。收集条件为pso>n。
public class Solution { int count = 0; public int countArrangement(int N) { if(N == 0) return 0; int[] visited = new int[N+1]; helper(visited,1,N); return count; } public void helper(int[] visited,int pos, int n){ if(pos>n){ count ++; return; } for(int i=1;i<=n;i++){ if(visited[i] == 0 && (pos%i==0 || i%pos==0)){ visited[i]=1; helper(visited,pos+1,n); visited[i]=0; } } }}