Backtrack
Backtrack是DFS的一种情势，根本写法雷同于Top Down DFS，但是引入状态回溯。
每次搜索一个分支，会起首记载当前节点的状态，实行完某个分支后，把状态回溯到记载的状态，再去实行别的的分支。
为什么要回溯状态？
假如不回溯，A分支的状态大概会被带入B分支，但他们又是独立的，所以会影响效果。
Backtrack()
- Base Case
- For each possibility p
a. Memorize current state
b. backtrack(next_state)
c. Restore current state
实例
/*给定一个仅包罗数字2-9的字符串，返回全部它能表示的字母组合。答案可以按 恣意次序 返回。给出数字到字母的映射如下（与电话按键雷同）。注意 1 不对应任何字母。示例 1：输入：digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：输入：digits = ""输出：[]示例 3：输入：digits = "2"输出：["a","b","c"]提示：0 <= digits.length <= 4digits 是范围 ['2', '9'] 的一个数字。 */public class LeetCode17 { public static void main(String[] args) { //todo 回溯-backtrack System.out.println(new Solution().letterCombinations("234")); System.out.println(new Solution2().letterCombinations("234")); System.out.println(new Solution3().letterCombinations("234")); System.out.println(new Solution4().letterCombinations("234")); System.out.println(new Solution5().letterCombinations("234")); } /* Backtrack是DFS的一种情势，根本写法雷同于Top Down DFS，但是引入状态回溯。 每次搜索一个分支，会起首记载当前节点的状态，实行完某个分支后，把状态回溯到记载的状态，再去实行别的的分支。 **为什么要回溯状态？** 假如不回溯，A分支的状态大概会被带入B分支，但他们又是独立的，所以会影响效果。 */ /* 回溯是一种通过穷举全部大概环境来找到全部解的算法。 假如一个候选解末了被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步调做出一些修改，并重新实行找到可行解。 */ static class Solution { Map<String, String> phone = new HashMap<String, String>() {{ put("2", "abc"); put("3", "def"); put("4", "ghi"); put("5", "jkl"); put("6", "mno"); put("7", "pqrs"); put("8", "tuv"); put("9", "wxyz"); }}; List<String> output = new ArrayList<String>(); public void backtrack(String combination, String next_digits) { //假如没有更多数字要查抄 if (next_digits.length() == 0) { //组合完成 output.add(combination); } else {//假如尚有数字要查抄 //遍历映射下一个可用数字的全部字母 String digit = next_digits.substring(0, 1); String letters = phone.get(digit); for (int i = 0; i < letters.length(); i++) { String letter = phone.get(digit).substring(i, i + 1); //将当前字母附加到组归并继续下一个数字 backtrack(combination + letter, next_digits.substring(1)); } } } public List<String> letterCombinations(String digits) { if (digits.length() != 0) backtrack("", digits); return output; } } static class Solution2 { public List<String> letterCombinations(String digits) { List<String> res = new ArrayList<>(); //使用一个聚集来存储全部的字母组合效果 if (digits == null || digits.length() == 0) return res; //将号码字母对应关系存储进Map Map<Character, String[]> map = new HashMap<Character, String[]>() {{ //存储为数组更好利用 put('2', new String[]{"a", "b", "c"}); put('3', new String[]{"d", "e", "f"}); put('4', new String[]{"g", "h", "i"}); put('5', new String[]{"j", "k", "l"}); put('6', new String[]{"m", "n", "o"}); put('7', new String[]{"p", "q", "r", "s"}); put('8', new String[]{"t", "u", "v"}); put('9', new String[]{"w", "x", "y", "z"}); }}; //界说一个队列来存储全部的组合效果 Queue<String> queue = new LinkedList<>(); //遍历Digits，取到对应号码对应的字母数组 for (int i = 0; i < digits.length(); i++) { queue_letterCombinations(queue, map.get(digits.charAt(i))); } //要求返回List res.addAll(queue); return res; } private Queue<String> queue_letterCombinations(Queue<String> queue, String[] letters) { //Queue<String> queue = new LinkedList<String>(); //初始界说的queue肯定是空的，所以这时间把第一个号码的字母放入队列 if (queue.size() == 0) { queue.addAll(Arrays.asList(letters)); } else { //对于背面到来字母，把queue出队列然后拼接以后进入队列 int queueLength = queue.size(); //记载本次须要举行出列组合的元素数目 for (int i = 0; i < queueLength; i++) { String s = queue.poll(); //队列头元素出队列 for (String letter : letters) { queue.add(s + letter); //将出来的队列元素和电话号码对应的字母依次举行拼接并添加进队列 } } } return queue; } } /* 我们可以使用队列的先辈先出特点，再共同循环完成标题要求。 比如，我们先将对应的字符 a,b,c依次放入队列中 之后再从队列中拿出第一个元素a，跟3对应的字符d,e,f挨个拼接 */ static class Solution3 { public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return new ArrayList<String>(); } //一个映射表，第二个位置是"abc“,第三个位置是"def"。。。 //这里也可以用map，用数组可以更节流点内存 //前两个只是占位 String[] letter_map = { "#", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; List<String> res = new ArrayList<>(); //先往队列中到场一个空字符 res.add(""); for (int i = 0; i < digits.length(); i++) { //由当前遍历到的字符，取字典表中查找对应的字符串 String letters = letter_map[digits.charAt(i) - '0']; int size = res.size(); //计算出队列长度后，将队列中的每个元素挨个拿出来 for (int j = 0; j < size; j++) { //每次都从队列中拿出第一个元素 String tmp = res.remove(0); //然后跟"def"如许的字符串拼接，并再次放到队列中 for (int k = 0; k < letters.length(); k++) { res.add(tmp + letters.charAt(k)); } } } return res; } } /* 方法一：回溯 方法1：深度优先搜索 - 关键词：全部组合 - 模式辨认：搜索算法 -自顶向下的递归实现神搜 -界说子题目 -在当前递归层团结子题目效果办理原题目 */ static class Solution4 { public List<String> letterCombinations(String digits) { List<String> combinations = new ArrayList<String>(); if (digits.length() == 0) { return combinations; } Map<Character, String> phoneMap = new HashMap<Character, String>() {{ put('2', "abc"); put('3', "def"); put('4', "ghi"); put('5', "jkl"); put('6', "mno"); put('7', "pqrs"); put('8', "tuv"); put('9', "wxyz"); }}; backtrack(combinations, phoneMap, digits, 0, new StringBuffer()); return combinations; } public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) { if (index == digits.length()) { combinations.add(combination.toString()); } else { char digit = digits.charAt(index); String letters = phoneMap.get(digit); int lettersCount = letters.length(); for (int i = 0; i < lettersCount; i++) { combination.append(letters.charAt(i)); backtrack(combinations, phoneMap, digits, index + 1, combination); combination.deleteCharAt(index); } } } } /* 回溯-队列 按层遍历 */ static class Solution5 { public List<String> letterCombinations(String digits) { List<String> combinations = new ArrayList<>(); //使用一个聚集来存储全部的字母组合效果 if (digits == null || digits.length() == 0) return combinations; //将号码字母对应关系存储进Map HashMap<Character, String[]> map = new HashMap<Character, String[]>() {{ //存储为数组更好利用 put('2', new String[]{"a", "b", "c"}); put('3', new String[]{"d", "e", "f"}); put('4', new String[]{"g", "h", "i"}); put('5', new String[]{"j", "k", "l"}); put('6', new String[]{"m", "n", "o"}); put('7', new String[]{"p", "q", "r", "s"}); put('8', new String[]{"t", "u", "v"}); put('9', new String[]{"w", "x", "y", "z"}); }}; //界说一个队列来存储全部的组合效果 Queue<String> queue = new LinkedList<>(); //遍历Digits，取到对应号码对应的字母数组 for (int i = 0; i < digits.length(); i++) { queue_letterCombinations(queue, map.get(digits.charAt(i))); } //要求返回List combinations.addAll(queue); return combinations; } private Queue<String> queue_letterCombinations(Queue<String> queue, String[] letters) { //Queue<String> queue = new LinkedList<String>(); //初始界说的queue肯定是空的，所以这时间把第一个号码的字母放入队列 if (queue.size() == 0) { queue.addAll(Arrays.asList(letters)); } else { //对于背面到来字母，把queue出队列然后拼接以后进入队列 int queueLength = queue.size(); //记载本次须要举行出列组合的元素数目 for (int i = 0; i < queueLength; i++) { String s = queue.poll(); //队列头元素出队列 for (String letter : letters) { queue.add(s + letter); //将出来的队列元素和电话号码对应的字母依次举行拼接并添加进队列 } } } return queue; } }}/*给定一个 没有重复 数字的序列，返回其全部大概的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] */public class LeetCode46 { //todo 回溯-backtrack public static void main(String[] args) { System.out.println(new Solution().permute(new int[]{1, 2, 3})); System.out.println(new Solution2().permute(new int[]{1, 2, 3})); } /* 回溯 深度优先遍历+状态重置 */ static class Solution { public List<List<Integer>> permute(int[] nums) { // 初始化输出列表 List<List<Integer>> res = new LinkedList<>(); // 将 nums 转换为列表，由于输出是列表的列表 ArrayList<Integer> path = new ArrayList<Integer>(); for (int num : nums) path.add(num); int n = nums.length; backtrack(n, path, res, 0); return res; } public void backtrack(int n, ArrayList<Integer> path, List<List<Integer>> res, int depth) { // 假如全部整数都用完了 if (depth == n) { //拷贝进去 res.add(new ArrayList<Integer>(path)); } for (int i = depth; i < n; i++) { // 维护动态数组 将第 i 个整数放在当前排列的首位 Collections.swap(path, depth, i); // 继续递归填下一个数 使用下一个整数来完成排列 backtrack(n, path, res, depth + 1); // 回溯 Collections.swap(path, depth, i); } } } /* 回溯 深度优先遍历+状态重置 状态：每个结点表示求解题目的差别阶段 状态变量： 1，递归到第几层 depth 2，已经选了哪些数 path 3，布尔数组 used */ static class Solution2 { public List<List<Integer>> permute(int[] nums) { int len = nums.length; List<List<Integer>> res = new ArrayList<>(); if (len == 0) return res; //栈 Deque<Integer> path = new ArrayDeque<>(); boolean[] used = new boolean[len]; dfs(nums, 0, path, used, res); return res; } private void dfs(int[] nums, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) { if (depth == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used) { continue; } //入栈 path.addLast(nums); used = true; //继续递归 dfs(nums, depth + 1, path, used, res); //回溯 path.removeLast(); used = false; } } }}/*给定一个可包罗重复数字的序列 nums ，按恣意次序 返回全部不重复的全排列。示例 1：输入：nums = [1,1,2]输出：[[1,1,2], [1,2,1], [2,1,1]]示例 2：输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示：1 <= nums.length <= 8-10 <= nums <= 10 */public class LeetCode47 { //todo 回溯-backtrack 参考17、46 public static void main(String[] args) { System.out.println(new Solution().permuteUnique(new int[]{1, 1, 2, 3})); System.out.println(new Solution2().permuteUnique(new int[]{1, 1, 2, 3})); } /* 回溯 深度优先遍历+状态重置 状态：每个结点表示求解题目的差别阶段 状态变量： 1，递归到第几层 depth 2，已经选了哪些数 path 3，布尔数组 used */ static class Solution { public List<List<Integer>> permuteUnique(int[] nums) { int len = nums.length; List<List<Integer>> res = new ArrayList<>(); if (len == 0) { return res; } // 排序（升序大概降序都可以），排序是剪枝的条件 Arrays.sort(nums); boolean[] used = new boolean[len]; // 使用 Deque 是 Java 官方 Stack 类的发起 Deque<Integer> path = new ArrayDeque<>(len); dfs(nums, 0, used, path, res); return res; } private void dfs(int[] nums, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) { if (depth == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; ++i) { if (used) { continue; } // 剪枝条件：i > 0 是为了包管 nums[i - 1] 故意义 // 写 !used[i - 1] 是由于 nums[i - 1] 在深度优先遍历的过程中刚刚被打消选择 if (i > 0 && nums == nums[i - 1] && !used[i - 1]) { continue; } path.addLast(nums); used = true; dfs(nums, depth + 1, used, path, res); // 回溯部门的代码，和 dfs 之前的代码是对称的 used = false; path.removeLast(); } } } /* 搜索回溯 */ static class Solution2 { boolean[] used; public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); used = new boolean[nums.length]; Arrays.sort(nums); backtrack(nums, res, 0, path); return res; } public void backtrack(int[] nums, List<List<Integer>> res, int depth, List<Integer> path) { if (depth == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; ++i) { if (used || (i > 0 && nums == nums[i - 1] && !used[i - 1])) { continue; } path.add(nums); used = true; backtrack(nums, res, depth + 1, path); used = false; path.remove(depth); } } }} |
