回溯——固定套路 | 面试算法12道

 

目录

输出二叉树所有路径

路径总和问题

组合总和问题

分割回文串

子集问题

排列问题

字母大小写全排列

单词搜索

复原IP地址

电话号码问题

括号生成问题

---

给我一种感觉是回溯需要画图思考是否需要剪枝。

元素个数n相当于树的宽度（横向），而每个结果的元素个数k相当于树的深度（纵向）。

枚举时，我们就是简单的暴力测试而已，一个个验证。

模板如下。

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素（画成树，就是树节点孩子的大小）){处理节点;backtracking();回溯，撤销处理结果;}}

输出二叉树所有路径

给你一个二叉树的根节点root ，按任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。

示例：

输入：root = [1,2,3,null,5]

输出：["1->2->5","1->3"]

class BinaryTreePaths {List<String> ans = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {dfs(root,new ArrayList<>());return ans;}private void dfs(TreeNode root, List<Integer> temp){if(root == null) return;temp.add(root.val);//如果是叶子节点记录结果if(root.left == null && root.right == null){ans.add(getPathString(temp));}dfs(root.left,temp);dfs(root.right,temp);temp.remove(temp.size()-1);}//拼接结果private String getPathString(List<Integer> temp){StringBuilder sb = new StringBuilder();sb.append(temp.get(0));for(int i = 1;i < temp.size(); ++i){sb.append("->").append(temp.get(i));}return sb.toString();}
}

路径总和问题

示例1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

输出：[[5,4,11,2],[5,8,4,5]]

class PathSum {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {LinkedList<Integer> path=new LinkedList<>();dfs(root,targetSum,path);return res;}public void dfs(TreeNode root,int targetSum,LinkedList<Integer> path){if(root==null){return;}//这个值有很关键的作用targetSum-=root.val;path.add(root.val);if(targetSum==0&&root.left==null&&root.right==null){res.add(new LinkedList(path));}dfs(root.left,targetSum,path);dfs(root.right,targetSum,path);path.removeLast();}
}

组合总和问题

给你一个无重复元素的整数数组candidates和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]

解释：

2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意2可以使用多次。

7 也是一个候选， 7 = 7 ，仅有这两种组合。

class CombinationSum {List<List<Integer>> res = new ArrayList<>(); //记录答案List<Integer> path = new ArrayList<>();  //记录当前正在访问的路径public List<List<Integer>> combinationSum(int[] candidates, int target) {dfs(candidates,0, target);return res;}public void dfs(int[] c, int u, int target) {if(target < 0){return ;} if(target == 0){res.add(new ArrayList(path));return ;}for(int i = u; i < c.length; i++){if( c[i] <= target)  {path.add(c[i]);//当前层将target减掉了一部分，也就是子结构只要找是否有满足(target -  c[i])就可以了dfs(c,i,target -  c[i]); // 因为可以重复使用，所以还是ipath.remove(path.size()-1); //回溯}}}
}

分割回文串

分割回文串，给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串 ，返回s所有可能的分割方案。回文串是正着读和反着读都一样的字符串。

示例1：

输入：s = "aab"

输出：[["a","a","b"],["aa","b"]]

class Partition {List<List<String>> lists = new ArrayList<>();Deque<String> deque = new LinkedList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return lists;}private void backTracking(String s, int startIndex) {//如果起始位置大于s的大小，说明找到了一组分割方案if (startIndex >= s.length()) {lists.add(new ArrayList(deque));return;}for (int i = startIndex; i < s.length(); i++) {//如果是回文子串，则记录if (isPalindrome(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);deque.addLast(str);} else {continue;}//起始位置后移，保证不重复backTracking(s, i + 1);deque.removeLast();}}//判断是否是回文串private boolean isPalindrome(String s, int startIndex, int end) {for (int i = startIndex, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}

子集问题

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

示例1：

输入：nums = [1,2,3]

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

class Subsets {// 存放符合条件结果的集合List<List<Integer>> result = new ArrayList<>();// 用来存放符合条件结果LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {//空集合也是一个子集if (nums.length == 0){result.add(new ArrayList<>());return result;}subsetsHelper(nums, 0);return result;}private void subsetsHelper(int[] nums, int startIndex){//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。result.add(new ArrayList<>(path));if (startIndex >= nums.length){ return;}for (int i = startIndex; i < nums.length; i++){path.add(nums[i]);subsetsHelper(nums, i + 1);path.removeLast();}}
}

排列问题

给定一个没有重复数字的序列，返回其所有可能的全排列。

输入: [1,2,3]

输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

class Permute {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {if (nums.length == 0){return result;}used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(int[] nums){if (path.size() == nums.length){result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++){if (used[i]){continue;}used[i] = true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}

字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。以任意顺序返回输出。

示例1：输入：s = "a1b2"

输出：["a1b2", "a1B2", "A1b2", "A1B2"]

class LetterCasePermutation {public List<String> letterCasePermutation(String s) {List<String> ans = new ArrayList<String>();dfs(s.toCharArray(), 0, ans);return ans;}public void dfs(char[] arr, int pos, List<String> res) {while (pos < arr.length && Character.isDigit(arr[pos])) {pos++;}if (pos == arr.length) {res.add(new String(arr));return;}arr[pos] ^= 32;dfs(arr, pos + 1, res);arr[pos] ^= 32;dfs(arr, pos + 1, res);}
}

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false。

示例1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

输出：true

class Exist {public boolean exist(char[][] board, String word) {char[] words = word.toCharArray();for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if (dfs(board, words, i, j, 0)) return true;}}return false;}boolean dfs(char[][] board, char[] word, int i, int j, int k) {if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;if (k == word.length - 1) return true;board[i][j] = '\0';boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);board[i][j] = word[k];return res;}
}

复原IP地址

有效IP地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0. 011. 255 .245"、"192.168.1.312" 和 "192.168@1.1" 是无效IP地址。给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址，这些地址可以通过在s中插入 '.' 来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。

// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法private Boolean isValid(String s, int start, int end) {if (start > end) {return false;}// 0开头的数字不合法if (s.charAt(start) == '0' && start != end) { return false;}int num = 0;for (int i = start; i <= end; i++) {// 遇到⾮数字字符不合法if (s.charAt(i) > '9' || s.charAt(i) < '0') { return false;}num = num * 10 + (s.charAt(i) - '0');if (num > 255) { // 如果⼤于255了不合法return false;}}return true;}

电话号码问题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母，9对应四个字母。

示例1：

输入：digits = "2| 3 4567"

输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class LetterCombinations {List<String> list = new ArrayList<>();public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return list;}//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backTracking(digits, numString, 0);return list;}//每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuildStringBuilder temp = new StringBuilder();//比如digits如果为"23",num 为0，则str表示2对应的 abcpublic void backTracking(String digits, String[] numString, int num) {//遍历全部一次记录一次得到的字符串if (num == digits.length()) {list.add(temp.toString());return;}//str 表示当前num对应的字符串String str = numString[digits.charAt(num) - '0'];for (int i = 0; i < str.length(); i++) {temp.append(str.charAt(i));backTracking(digits, numString, num + 1);//剔除末尾的继续尝试temp.deleteCharAt(temp.length() - 1);}}
}

括号生成问题

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

class GenerateParenthesis {public List<String> generateParenthesis(int n) {List<String> ans = new ArrayList<String>();backtrack(ans, new StringBuilder(), 0, 0, n);return ans;}/*** @param ans 当前递归得到的结果* @param cur 当前的括号串* @param open   左括号已经使用的个数* @param close  右括号已经使用的个数* @param max    序列长度最大值*/public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {if (cur.length() == max * 2) {ans.add(cur.toString());return;}//本题需要两次回溯，比较少见的情况if (open < max) {cur.append('(');backtrack(ans, cur, open + 1, close, max);cur.deleteCharAt(cur.length() - 1);}if (close < open) {cur.append(')');backtrack(ans, cur, open, close + 1, max);cur.deleteCharAt(cur.length() - 1);}}
}