回溯算法的关键在于递归，并在一个递归结束后去掉传入的数据
Leetcode46 全排列
思路： 最经典的回溯算法。 使用双重循环，交换后递归至下一层，递归完后交换回来， 层数取决于外层循环（ｉ＋１）
代码：
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new LinkedList(); List<Integer> numsList = new ArrayList(); for(int e : nums) numsList.add(e); permutation(result, numsList, 0); return result; } private void permutation(List<List<Integer>> result, List<Integer> nums, int li){ result.add(new ArrayList(nums)); // 效率主要提高在这，native 拷贝方法会比写 for 循环拷贝要快 // 从li开始顺序两两交换 for(int i = li; i < nums.size(); ++i) { for(int j = i+1; j < nums.size(); ++j) { Collections.swap(nums, i, j); permutation(result, nums, i+1); Collections.swap(nums, i, j); } } } }leetcode22 括号生成
思路： 无需删除错误条件的情况下。 另一种思路，每次递归生成一个新的结果。 抓住先左括号后右括号的思路。
代码：
class Solution { public List<String> generateParenthesis(int n) { List<String> list = new ArrayList<>(); String str = new String(); generate(list,str,n,n); return list; } public void generate(List<String> list,String str,int left,int right){ if(left==0&&right==0){ list.add(str); return; } if(left>0){ generate(list,str+'(',left-1,right); } if(right>left){ generate(list,str+')',left,right-1); } } }leetcode131 分割回文串
思路： 符合回文条件就添加数据，判断到结尾后再取出 也是经典的回溯算法。 通过了存储判断过的情况加快速度
代码：
import java.util.ArrayList; import java.util.List; /** * 回溯算法 * 时间复杂度：3ms，100% * 空间复杂度：38.6MB，97.10% */ public class Solution_131 { /* 用来保存从任意一位置至任意一位置的子串是否是回文串，类似于动态规划中保存之前的状态来减小时间复杂度 不同之处在于这里的状态并没有发生转移，所以不算是动态规划与回溯算法的结合 这一步是优化时间复杂度的关键 */ int[][] dp; public List<List<String>> partition(String s) { List<List<String>> res = new ArrayList<>(); if (null == s || s.length() == 0) { return res; } int length = s.length(); /* 它是一个二维矩阵，有三种状态值： 0表示之前还没有计算过 1表示从下表i到j的子串是回文串 2表示不是回文串 我们只用到了数组的右上半部分 当然这里也可以使用char数组，空间复杂度更低 */ dp = new int[length][length]; //初始化，单个字符的肯定是回文串 for (int i = 0; i < length; i++) { dp[i][i] = 1; } ArrayList<String> templist = new ArrayList<>(); helper(res, templist, s, length, 0); return res; } /** * 回溯算法 * * @param res 结果集 * @param templist 中间list * @param s 字符串 * @param length 字符串长度 * @param index 从当前位置向后组合判断 */ private void helper(List<List<String>> res, ArrayList<String> templist, String s, int length, int index) { //走到这一步就表示走到了最后，添加到结果集 if (index == length) { res.add(new ArrayList<>(templist));//一定要重新new一个对象，templist可以得到重用 } //走到某一步有若干的选择继续走下一步 for (int i = index; i < length; i++) { if (isPalindrome(s, index, i)) { templist.add(s.substring(index, i + 1)); helper(res, templist, s, length, i + 1); templist.remove(templist.size() - 1);//回溯算法中回退一定要记得这一步 } } } //判断是否是回文串，这里首先需要到保存的状态中查看是否之前已经有了，优化时间复杂度 private boolean isPalindrome(String s, int from, int to) { if (dp[from][to] == 1) { return true; } else if (dp[from][to] == 2) { return false; } else { for (int i = from, j = to; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { dp[from][to] = 2; return false; } } dp[from][to] = 1; return true; } } }leetcode93 复制IP地址
思路： 类似上题。 循环范围的处理不一样 下界取最大值，在前置值加一和长度减去３（ＩＰ最长情况）× 剩下的节点数中。 上界区最小值，在长度间剩余节点数（每个节点取最小值１）和前置值加三间。 取到尾节点（剩一个节点）时，额外计算一轮，将所有数据使用 join 方法拼接起来加入 res
代码：
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; /** * 时间复杂度4ms，91.56% */ public class Solution_93 { /* 用来保存从任意一位置至任意一位置的子串是否是有效的，类似于动态规划中保存之前的状态来减小时间复杂度 不同之处在于这里的状态并没有发生转移，所以不算是动态规划与回溯算法的结合 这一步是优化时间复杂度的关键 */ int[][] dp; public List<String> restoreIpAddresses(String s) { ArrayList<String> res = new ArrayList<>(); if (null == s) { return res; } int length = s.length(); if (length < 4 || length > 12) { return res; } /* 它是一个二维矩阵，有三种状态值： 0表示之前还没有判断过 1表示从下表i到j的子串是有效的 2表示不是有效的 我们只用到了右上半部分，当然这里也可以使用char数组，空间复杂度更低 */ dp = new int[length][length]; //初始化，单个字符的肯定是有效的 for (int i = 0; i < length; i++) { dp[i][i] = 1; } LinkedList<String> templist = new LinkedList<>(); dfs(res, templist, s, length, -1, 3); return res; } /** * 回溯算法，每添加一个点，算是解空间路径中的一层 * * @param res 结果集 * @param templist 用来存放中间结果的list，需要在每一步路径回退的时候移除最后添加进去的string * @param prePos 前一个点放置的位置，初始值为-1 * @param dotnum 当前需要方式的点的个数 */ private void dfs(ArrayList<String> res, LinkedList<String> templist, String s, int length, int prePos, int dotnum) { //界定当前点能够放置的位置的上下界 int minPos = Math.min(length - 1 - dotnum, prePos + 3); int maxPos = Math.max(prePos + 1, length - 1 - 3 * dotnum); for (int curPos = maxPos; curPos <= minPos; curPos++) { String substr = s.substring(prePos + 1, curPos + 1); if (isValid(substr, prePos + 1, curPos)) { templist.add(substr); if (dotnum == 1) {//当放置完最后一个点的时候，还需要将最后一段添加进去 substr = s.substring(curPos + 1, length); if (isValid(substr, curPos + 1, length - 1)) { templist.add(substr); res.add(String.join(".", templist)); templist.removeLast();//回溯算法中回退需要的步骤 } } else { dfs(res, templist, s, length, curPos, dotnum - 1); } templist.removeLast();//回溯算法中回退需要的步骤 } } } //判断是否是有效的，这里首先需要到保存的状态中查看是否之前已经有了，优化时间复杂度 private boolean isValid(String substr, int from, int to) { if (to - from > 2) { return false; } if (dp[from][to] == 1) { return true; } else if (dp[from][to] == 2) { return false; } else { if (substr.charAt(0) != '0' && Integer.valueOf(substr) <= 255) {//值在0-255之间，且如果是两位以上，开头不能是0 dp[from][to] = 1; return true; } else { dp[from][to] = 2; return false; } } } }