本文共 9551 字，大约阅读时间需要 31 分钟。
wiki上面是这么说的
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。其实通俗点讲我觉得回溯法就是使用在对一组数据求其在某种条件下所有的可能性组合。
常见的题目通常是给一个数组数据或者字符串，然后求其所有组成。所以有如下的通用解题模板
Class Solation{ public List > backtrack(int[] a) { List > list = new ArrayList<>(); //Arrays.sort(a);//当a中存在重复值。而重复值不能使用的时候。就要进行排序。对使用过的重复值不再使用 backTrackTemp(list, new ArrayList<>(), a, .....)//其中的"...."表示其他限定条件(根据条件限定而存在与否) return lis}//回溯过程private static void backTrackTemp(List
这里对backTrackTemp(list, new ArrayList<>(), a, .....)中的参数说个说明
接下来我们通过一些例子来看看是怎么使用这个demo的
1、数组中不存在重复数值的
题目如下：Given a set of distinct integers, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.Example:Input: nums = [1,2,3]Output:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]
class Solution { public List > subsets(int[] nums) { List > list = new ArrayList<>(); backTracking(list,new ArrayList<>(),nums,0);//list,临时list,额外条件，因为subSet是不能存在重复的，所以要有start值。因为在set中只要元素相同，即使顺序不用也是一致的。跟排列不一样 return list; } //没有start就找不到终止条件了 private static void backTracking(List > list, ArrayList tempList, int[] nums,int start){ list.add(new ArrayList<>(tempList));//每一组都添加，不用条件,这一步已经把空的也加进去 for(int i = start; i < nums.length; i++) { tempList.add(nums[i]); backTracking(list,tempList,nums,i+1); tempList.remove(tempList.size() - 1); } }}
2、数组中存在重复数值的，但是结果不能存在重复值
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.Example:Input: [1,2,2]Output:[ [2], [1], [1,2,2], [2,2], [1,2], []]
class Solution { public List > subsetsWithDup(int[] nums) { List > list = new ArrayList<>(); Arrays.sort(nums); backTracking(list, new ArrayList<>(), nums, 0); return list; } //因为这个回溯法是判断以每一个数为准的所有组成 private static void backTracking(List > list, List tempList, int[] nums, int startIndex) { //方法一：判断是否已经存在 // if(!list.contains(tempList)) list.add(new ArrayList<>(tempList)); for(int i = startIndex; i < nums.length; i++) { if(i > startIndex && nums[i] == nums[i-1]) continue;//方法二.跳过重复的数字 tempList.add(nums[i]); backTracking(list, tempList, nums, i + 1); tempList.remove(tempList.size()-1); } }}
1、不存在重复值的排列
Given a collection of distinct integers, return all possible permutations.Example:Input: [1,2,3]Output:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
class Solution { public static List > permute(int[] nums) { List > list = new ArrayList<>(); backtrack(list, new ArrayList<>(), nums,new boolean[nums.length]);//回溯法的三要素，条件值nums,存储结果数组list,临时结果(判断用的)。还有其他的额外控制条件 return list; } private static void backtrack(List > list, List tempList, int [] nums, boolean[] used){ if(tempList.size() == nums.length){ //终止条件 list.add(new ArrayList<>(tempList));//这边要new的原因是因为下面的对象引用还存在。更改会改变这个list里面的值 } else{ for(int i = 0; i < nums.length; i++){ //回溯过程 if(used[i] == true) continue; else { tempList.add(nums[i]); used[i] = true;//访问过了就不要再访问 backtrack(list, tempList, nums, used); used[i] = false;//一次回溯后就要将访问的重新置为未访问的 tempList.remove(tempList.size() - 1); } } } } }
2、存在重复数字
Given a collection of numbers that might contain duplicates, return all possible unique permutations.Example:Input: [1,1,2]Output:[ [1,1,2], [1,2,1], [2,1,1]]
class Solution { public List > permuteUnique(int[] nums) { List > list = new ArrayList<>(); Arrays.sort(nums); backTracking(list, new ArrayList<>(), nums, new boolean[nums.length]); return list; } private void backTracking(List > list, ArrayList tempList, int[] nums, boolean[] used){ //终止条件 //if(tempList.size() == nums.length && !list.contains(tempList))//用contains判断是否已经存在 if(tempList.size() == nums.length) list.add(new ArrayList(tempList)); //回溯条件 for(int i = 0; i < nums.length; i++) { if((i > 0 && nums[i] == nums[i - 1] && used[i-1]==false)||(used[i] == true))//访问过了就不再访问且判断重复的去掉 continue; tempList.add(nums[i]);//添加到tempList中 used[i] = true;//置为访问过的 backTracking(list, tempList, nums, used);//以当前点回溯 used[i] = false; tempList.remove(tempList.size() - 1);//返回上一层 } }}
1、不存在重复值的
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.The same repeated number may be chosen from candidates unlimited number of times.Note:All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.Example 1:Input: candidates = [2,3,6,7], target = 7,A solution set is:[ [7], [2,2,3]]Example 2:Input: candidates = [2,3,5], target = 8,A solution set is:[ [2,2,2,2], [2,3,3], [3,5]]
class Solution { public List > combinationSum(int[] candidates, int target) { List > list = new ArrayList<>(); backTracking(list, new ArrayList<>(), candidates, target, 0); return list; } private static void backTracking(List > list, ArrayList tempList, int[] candidates, int target, int startIndex) { if(target < 0)return;//当不符合的时候，返回 if(target == 0)list.add(new ArrayList<>(tempList));//符合的时候添加到集合 for(int i = startIndex; i < candidates.length; i++) { tempList.add(candidates[i]); //回溯，因为一个节点可以重复使用，所以还是以i为当前节点 backTracking(list, tempList, candidates, target - candidates[i], i); tempList.remove(tempList.size() - 1); } }}
2、存在重复值的
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.Each number in candidates may only be used once in the combination.Note:All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.Example 1:Input: candidates = [10,1,2,7,6,1,5], target = 8,A solution set is:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]Example 2:Input: candidates = [2,5,2,1,2], target = 5,A solution set is:[ [1,2,2], [5]]
class Solution { public List > combinationSum2(int[] candidates, int target) { List > list = new ArrayList<>(); Arrays.sort(candidates); backTracking(list, new ArrayList<>(), candidates, target, 0); return list; } private static void backTracking(List > list, ArrayList tempList, int[] candidates, int target, int startIndex ) { if(target < 0)return; if(target == 0)list.add(new ArrayList<>(tempList));//终止条件 for(int i = startIndex; i < candidates.length; i++) { if(i > startIndex && candidates[i] == candidates[i-1])//去掉重复的 continue; tempList.add(candidates[i]); backTracking(list, tempList, candidates, target - candidates[i],i+1);//每个数字只能用一次 tempList.remove(tempList.size() - 1); } }}
Given a string s, partition s such that every substring of the partition is a palindrome.Return all possible palindrome partitioning of s.Example:Input: "aab"Output:[ ["aa","b"], ["a","a","b"]]
class Solution { public List > partition(String s) { List > list = new ArrayList<>(); backTracking(list, new ArrayList<>(), s, 0); return list; } private static void backTracking(List > list, List tempList, String s, int startIndex){ //终止条件，也就是加入list的条件,startIndex来到最后一个字符。遍历完了 if(startIndex == s.length()) list.add(new ArrayList<>(tempList)); for(int i = startIndex; i < s.length(); i++) { if(isPartition(s, startIndex, i))//如果是回文串, { tempList.add(s.substring(startIndex,i+1));//加入到templist.substring(start, end),end是取不到的 backTracking(list, tempList, s, i+1);//当前部分是回文串就不会再使用 tempList.remove(tempList.size() - 1); } } } //判断是否是回文串 private static boolean isPartition(String s, int left, int right) { while(left <= right) { if(s.charAt(left++) != s.charAt(right--)) return false; } return true; }}
我们通过subset(所有可能子集合)，Permutations(所有可能排序)， Combination Sum(可以组合成一个数的所有情况)、Palindrome Partitioning（一个字符串拆成都是回文串的所有个数）。
1、从中可以发现。如果跟顺序没有关系的，则应该加startIndex,而如果有关系则都应该从0开始。因为不同位置从0开始都是不同的。 2、如果在一次中访问过的可能再访问到且不能再访问，则应该设置一个used[]数组来保存每次访问过的元素。当一次回溯完时则应该放开。 3、如果存在重复的数字。则应该先排序，排序可以更好的解决去掉重复值的情况。转载地址：http://sxrai.baihongyu.com/