《代码随想录》刷题笔记——回溯篇【java实现】

组合

https://leetcode.cn/problems/combinations/description/

public List<List<Integer>> combine(int n, int k) {List<List<Integer>> result = new ArrayList<>();// 存储搜索路径List<Integer> path = new ArrayList<>();// 从1开始递归backtrack(n, k, 1, path, result);return result;
}void backtrack(int n, int k, int startNum, List<Integer> path, List<List<Integer>> result) {if (path.size() == k) {// --if-- 组合的元素个数=k，说明找到了新的解，存储到result中List<Integer> clone = new ArrayList<>(k);for (Integer num : path) {clone.add(num);}result.add(clone);return;}for (int num = startNum; num <= n; num++) {// --for--遍历加下来的元素// 将遍历到的元素添加到搜索路径中path.add(num);// 递归，开始数量+1backtrack(n, k, num + 1, path, result);// 移除刚刚添加的数量path.remove(path.size() - 1);}
}

List<Integer> clone = new ArrayList<>(k);
for (Integer num : path) {clone.add(num);
}
result.add(clone);

上面的实现可以简化为

result.add(new ArrayList<>(path));

通过查看源码可以发现，构造方法传入集合的时候，JDK会自动帮我们做克隆操作

/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/
public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}
}

通过提交运行结果可以发现，上面的实现执行用时比较长，这是为什么呢？

假设n=5,k=3，组合可选元素为1,2,3,4,5

• 当path=[]时，组合的第一个元素为4，后面只有一个5，继续递归遍历，也只能找到两个元素的组合，无法找找到达到长度要求的组合（4、5无需遍历）；
• 当path=[1]时，组合的第二个元素为5，后面没有元素，无法找找到达到长度要求的组合（5无需遍历）；

因此通过减少部分遍历来加快代码速度

public List<List<Integer>> combine(int n, int k) {List<List<Integer>> result = new ArrayList<>();// 存储搜索路径List<Integer> path = new ArrayList<>();// 从1开始递归backtrack(n, k, 1, path, result);return result;
}void backtrack(int n, int k, int startNum, List<Integer> path, List<List<Integer>> result) {if (path.size() == k) {// --if-- 组合的元素个数=k，说明找到了新的解，存储到result中result.add(new ArrayList<>(path));return;}for (int num = startNum; num <= n - (k - path.size()) + 1; num++) {// --for--遍历加下来的元素// 将遍历到的元素添加到搜索路径中path.add(num);// 递归，开始数量+1backtrack(n, k, num + 1, path, result);// 移除刚刚添加的数量path.remove(path.size() - 1);}
}

在创建List<Integer> path = new ArrayList<>();，因为path的长度已知，因此可以在初始化集合的时候传入集合长度，避免后面发生集合扩容，List<Integer> path = new ArrayList<>(k);

组合总和 III

https://leetcode.cn/problems/combination-sum-iii/description/

public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtrack(k, n, 1, result, path, 0);return result;
}private void backtrack(int k, int n, int startNum, List<List<Integer>> result, List<Integer> path, int sum) {if (path.size() == k) {// --if-- 搜索到的组合元素个数为kif (sum == n) {// --if-- sum等于n，存储组合result.add(new ArrayList<>(path));} else {// --if-- 元素个数已经为3，无需再往下递归，否则，元素个数超出k了，再搜索也是白费return;}}for (int i = startNum; i <= 9; i++) {path.add(i);backtrack(k, n, i + 1, result, path, sum + i);path.remove(path.size() - 1);}
}

【剪枝优化】

• 剪枝1：path.size()>k
• 剪枝2：sum>n
• 剪枝3：无效组合起点，类似上一题，i <= 10- (k - path.size())

public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtrack(k, n, 1, result, path, 0);return result;
}private void backtrack(int k, int n, int startNum, List<List<Integer>> result, List<Integer> path, int sum) {if (path.size() == k) {// --if-- 搜索到的组合元素个数为kif (sum == n) {// --if-- sum等于n，存储组合result.add(new ArrayList<>(path));} else {// --if-- 元素个数已经为3，无需再往下递归，否则，元素个数超出k了，再搜索也是白费return;}} else if (sum > n) {// --if-- 搜索到的组sum已经大于n，无需再往下搜索return;}for (int i = startNum; i <= 10- (k - path.size()) ; i++) {path.add(i);backtrack(k, n, i + 1, result, path, sum + i);path.remove(path.size() - 1);}
}

电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

public List<String> letterCombinations(String digits) {if (digits.length() == 0) {return new ArrayList<>();}// 先将字符串转化为char数组，方便遍历操作char[] charArray = digits.toCharArray();// 存储结果List<String> result = new ArrayList<>();// 存储搜索组合（为什么使用数组呢，因为组合的元素数量是没有变化的，而且后面需要将元素组合转化为字符串，使用char数组更加方便）char[] path = new char[digits.length()];// 从1开始递归backtrack(charArray, 0, path, result);return result;
}void backtrack(char[] charArray, int charIndex, char[] path, List<String> result) {if (charIndex == charArray.length) {// --if-- 数字已经遍历完成，存储结果result.add(new String(path));return;}char numChar = charArray[charIndex];// 根据输入的数字，转化为对应的字符数组char[] chooseCharArr = null;switch (numChar) {case '2':chooseCharArr = new char[]{'a', 'b', 'c'};break;case '3':chooseCharArr = new char[]{'d', 'e', 'f'};break;case '4':chooseCharArr = new char[]{'g', 'h', 'i'};break;case '5':chooseCharArr = new char[]{'j', 'k', 'l'};break;case '6':chooseCharArr = new char[]{'m', 'n', 'o'};break;case '7':chooseCharArr = new char[]{'p', 'q', 'r', 's'};break;case '8':chooseCharArr = new char[]{'t', 'u', 'v'};break;case '9':chooseCharArr = new char[]{'w', 'x', 'y', 'z'};break;}// 循环字符数组，挑选一个，并进入下一个数字对应的字符挑选for (int i = 0; i < chooseCharArr.length; i++) {path[charIndex] = chooseCharArr[i];backtrack(charArray, charIndex + 1, path, result);// 这里不需要回溯操作，因为下一次循环会主动将 path[charIndex] 替换成另一个元素}
}

【代码随想录实现】

//设置全局列表存储最后的结果
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;}//每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
StringBuilder temp = new StringBuilder();//比如digits如果为"23",num 为0，则str表示2对应的 abc
public 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);}
}

组合总和

https://leetcode.cn/problems/combination-sum/description/

public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtrack(candidates, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int target, int startIndex,List<List<Integer>> result, List<Integer> path) {if (target == 0) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {// 计算剩下的target最多还可以容纳多少个 candidates[i] int num = target / candidates[i];// 循环取不同个数 candidates[i] 的情况// 注意j从1开始，j=0的情况其实在i的循环中已经考虑到了，例如当i等于startIndex+1时，实际上就是startIndex对应的元素j=0for (int j = 1; j <= num; j++) {// 将j个元素添加到搜索路径中for (int k = 0; k < j; k++) {path.add(candidates[i]);}backtrack(candidates, target - candidates[i] * j, i + 1, result, path);// 将j个元素从搜索路径中移除for (int k = 0; k < j; k++) {path.remove(path.size() - 1);}}}
}

从结果可以分析出来，上面的代码还有效率问题

其中的一个原因就是如下代码，每次需要添加j个元素，然后移除j个元素

// 将j个元素添加到搜索路径中
for (int k = 0; k < j; k++) {path.add(candidates[i]);
}// 将j个元素从搜索路径中移除
for (int k = 0; k < j; k++) {path.remove(path.size() - 1);
}

改成下面的代码，效率会更好一点

public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtrack(candidates, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int target, int startIndex,List<List<Integer>> result, List<Integer> path) {if (target == 0) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (target >= candidates[i]) {path.add(candidates[i]);backtrack(candidates, target - candidates[i], i, result, path);path.remove(path.size() - 1);}}
}

最后还存在一个剪枝策略，就是先将candidates升序排序，当遇到一个candidates[i]>target时，直接break出循环即可

 public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();Arrays.sort(candidates);backtrack(candidates, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int target, int startIndex,List<List<Integer>> result, List<Integer> path) {if (target == 0) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (target >= candidates[i]) {path.add(candidates[i]);backtrack(candidates, target - candidates[i], i, result, path);path.remove(path.size() - 1);} else {break;}}
}

不过跑了很多次，还没有前面的效率高，可能是排序也比较耗时

组合总和II

https://leetcode.cn/problems/combination-sum-ii/description/

思路

如下图所示，常规的回溯方法会导致搜索到重复的组合，题目中要求不能出现重复组合。可以做一些去重操作来解决这个问题，但是性能肯定不好。我们应该在搜索的时候进行剪枝。

如下图所示，分支2 其实已经被 分支1 包含，因此算法在搜索过程，无需搜索分支2

如何识别出分支2呢，一个明显的特征是，candidates[1] = candidates[0] = 2，那当candidates[i] = candidates[i-1]时，就把i对应分支剪掉？

答案是不允许，因为这样的话，会导致分支1也没有搜索完全。如下图所示，分支a 和 分支b 都会被剪掉。如果target=7 的话，组合[2,2,3]就搜索不到了。因此需要区分 分支a 和 分支b ，分支b才是要被剪枝的。

那么如何区分 分支a 和 分支b 呢？我使用一个数组useArr来帮助区分，useArr[i]表示candidates[i]在当前搜索组合中是否被使用。如下图所示，搜索过程中useArr的变化如下图所示。从图中可以很容易发现，分支a和分支b的useArr不一样，准确来说，是useArr[i-1]不一样，分支a对应的useArr[i-1]=1，而分支b对应的useArr[i-1]=0。因此当i > 0 && useArr[i - 1] == 0 && candidates[i - 1] == candidates[i]时，进行剪枝。注意，在搜索之前需要先对candidates进行升序排序，才通过判断i和i-1对应的元素是否相同。

代码实现

public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();// 存储组合使用的元素，1说明元素被使用，0说明元素没有被使用int[] useArr = new int[candidates.length];// 先将数组的值升序排序Arrays.sort(candidates);backtrack(candidates, useArr, target, 0, result, path);return result;
}private void backtrack(int[] candidates, int[] useArr, int target, int startIndex,List<List<Integer>> result, List<Integer> path) {if (target == 0) {result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (target < candidates[i]) {// target很小了，candidates后的数只会更大，所以可以breakbreak;}// 如果 candidates[i - 1] == candidates[i] ，说明同一层遍历到和之前的元素一样。如果useArr[i - 1] == 0，进行剪枝if (i > 0 && useArr[i - 1] == 0 && candidates[i - 1] == candidates[i]) {continue;}// 使用了candidates[i]useArr[i] = 1;path.add(candidates[i]);backtrack(candidates, useArr, target - candidates[i], i + 1, result, path);path.remove(path.size() - 1);// 去除candidates[i]的使用useArr[i] = 0;}
}

分割回文串※

https://leetcode.cn/problems/palindrome-partitioning/description/

思路

字符串分割

public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();char[] charArray = s.toCharArray();backtrack(result, path, charArray, 0);return result;
}private void backtrack(List<List<String>> result, List<String> path, char[] charArray, int startIndex) {if (startIndex == charArray.length) {// --if-- 字符串切割完成了result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < charArray.length; i++) {String s = "";// 截取[startIndex,i]对应子串for (int j = startIndex; j <= i; j++) {s += charArray[j];}// 将子串添加到path中path.add(s);// 递归处理剩下的子串backtrack(result, path, charArray, i + 1);// 回溯path.remove(path.size() - 1);}
}

当然上面的代码是生成所有的切割方案，并没有判断切割出来的子串是否符合回文串要求

回文串判断

判断一个字符串非常简单，使用双指针法。一个指针从头开始，一个指针从尾开始，判断两个指针对应的字符是否相同即可，如果出现不相同，说明字符串不是回文串。

private boolean isPalindromeSubStr(String s) {int start = 0;int end = s.length() - 1;while (start < end) {if (s.charAt(start++) != s.charAt(end--)) {return false;}}return true;
}

【总代码】

public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();char[] charArray = s.toCharArray();backtrack(result, path, charArray, 0);return result;
}private void backtrack(List<List<String>> result, List<String> path, char[] charArray, int startIndex) {if (startIndex == charArray.length) {// --if-- 字符串切割完成了result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < charArray.length; i++) {String s = "";for (int j = startIndex; j <= i; j++) {s += charArray[j];}// 判断子串是否为回文串，如果不是的，遍历下一个回文串if (isPalindromeSubStr(s) == false) {continue;}path.add(s);backtrack(result, path, charArray, i + 1);path.remove(path.size() - 1);}
}private boolean isPalindromeSubStr(String s) {int start = 0;int end = s.length() - 1;while (start < end) {if (s.charAt(start++) != s.charAt(end--)) {return false;}}return true;
}

通过结果，可以发现计算效率非常低，因为在搜索过程中，不断使用字符串拼接

效率优化※

直接使用substring

public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();backtrack(result, path, s, 0);return result;
}private void backtrack(List<List<String>> result, List<String> path, String s, int startIndex) {if (startIndex == s.length()) {// --if-- 字符串切割完成了result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {// 判断子串是否为回文串，如果不是的，遍历下一个回文串String str = s.substring(startIndex, i + 1);if (isPalindromeSubStr(str) == false) {continue;}path.add(str);backtrack(result, path, s, i + 1);path.remove(path.size() - 1);}
}private boolean isPalindromeSubStr(String s) {int start = 0;int end = s.length() - 1;while (start < end) {if (s.charAt(start++) != s.charAt(end--)) {return false;}}return true;
}

效率提高了一点点

多跑一次，结果完全不同，所以大家不能太相信leetcode的数据统计。同一段代码在计算机中跑，运行时间有波动非常正常

性能还有优化的空间，还可以使用动态规划来进行优化，等学完动态规划，再回来改进

复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/description/

public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();List<String> path = new ArrayList<>();char[] charArray = s.toCharArray();backtrack(result, path, charArray, 0);return result;
}private void backtrack(List<String> result, List<String> path, char[] charArray, int startIndex) {if (startIndex == charArray.length && path.size() == 4) {// --if-- 字符串切割完成了，且符合ip形式，就存储ipStringBuilder ipSb = new StringBuilder();for (int i = 0; i < path.size() - 1; i++) {ipSb.append(path.get(i) + ".");}ipSb.append(path.get(path.size() - 1));result.add(ipSb.toString());return;} else if (path.size() > 4) {// --if-- 超过4个整数了，ip不合法return;}StringBuilder sb = new StringBuilder();for (int i = startIndex; i < charArray.length; i++) {sb.append(charArray[i]);// 判断子串是否为回文串，如果不是的，遍历下一个回文串if (isReasonable(sb.toString()) == false) {break;}path.add(sb.toString());backtrack(result, path, charArray, i + 1);path.remove(path.size() - 1);}
}private boolean isReasonable(String string) {// 不能含有前导 0if (string.length() > 1 && string.charAt(0) == '0') {return false;}// 每个整数位于 0 到 255 之间组成int num = Integer.parseInt(string);if (num > 255) {return false;}return true;
}

优化版本

统一使用一个StringBuilder

String temp;public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();StringBuilder sb = new StringBuilder();backtrack(result, sb, s, 0, 0);return result;
}/*** 回溯方法** @param result     记录结果集* @param sb         记录当前ip* @param s          原字符串* @param startIndex 开始索引* @param splitNum   逗号分割数量*/
private void backtrack(List<String> result, StringBuilder sb, String s, int startIndex, int splitNum) {if (startIndex == s.length() && splitNum == 4) {// --if-- 字符串切割完成了，且符合ip形式，就存储ipresult.add(sb.toString());return;} else if (splitNum == 4) {// --if-- 超过4个整数了，ip不合法return;}for (int i = startIndex; i < s.length(); i++) {if (i - startIndex >= 1 && s.charAt(startIndex) == '0') {// --if-- 当前网段长度>1，且含有前导 0，不合法ip，breakbreak;}if (i - startIndex >= 3) {// --if-- 当前网段长度>3，不合法ip，breakbreak;}// 截取字符串作为网段，注意是左闭右开，所以i+1temp = s.substring(startIndex, i + 1);if (Integer.parseInt(temp) > 255) {// --if-- 当前网段值>255，不合法ip，breakbreak;}// 将当前网段添加到ip中sb.append(temp);// 如果逗号数量 < 3（一个ip，网段最多4个，逗号最多3个），拼接一个逗号if (splitNum < 3) {sb.append(".");}// 递归backtrack(result, sb, s, i + 1, splitNum + 1);// 回溯，删除最后一个网段，例如现在是255.255.11.13，回溯之后为 255.255.11.sb.delete(startIndex + splitNum, sb.length());}
}

子集

https://leetcode.cn/problems/subsets/description/

注意：题目说了nums中的所有元素各不相同，所以下面的代码没有必要去重

public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtrack(result, path, nums, 0);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int startIndex) {// 任何集合都要存储，没有说需要满足什么条件才可以存储result.add(new ArrayList<>(path));// 当 startIndex = nums长度 的时候，本来需要return，但是下面的循环不会进行，所以无需把这部分代码写出来了for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);backtrack(result, path, nums, i + 1);path.remove(path.size() - 1);}
}

子集 II

https://leetcode.cn/problems/subsets-ii/description/

使用usedArr辅助去重

注意，这道题目和上面的不同，数组里面含有重复元素，需要去重操作，其实就和 组合总和II 的思路一样

public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();Arrays.sort(nums);int[] useArr = new int[nums.length];backtrack(result, path, nums, 0, useArr);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int startIndex, int[] useArr) {// 任何集合都要存储，没有说需要满足什么条件才可以存储result.add(new ArrayList<>(path));// 当 startIndex = nums长度 的时候，本来需要return，但是下面的循环不会进行，所以无需把这部分代码写出来了for (int i = startIndex; i < nums.length; i++) {// 去重if (i > 0 && useArr[i - 1] == 0 && nums[i - 1] == nums[i]) {continue;}path.add(nums[i]);useArr[i] = 1;backtrack(result, path, nums, i + 1, useArr);path.remove(path.size() - 1);useArr[i] = 0;}
}

不使用usedArr辅助去重

其实这道题还可以不用use数组

public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();Arrays.sort(nums);backtrack(result, path, nums, 0);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int startIndex) {// 任何集合都要存储，没有说需要满足什么条件才可以存储result.add(new ArrayList<>(path));// 当 startIndex = nums长度 的时候，本来需要return，但是下面的循环不会进行，所以无需把这部分代码写出来了for (int i = startIndex; i < nums.length; i++) {// 去重if (i > startIndex && nums[i - 1] == nums[i]) {continue;}path.add(nums[i]);backtrack(result, path, nums, i + 1);path.remove(path.size() - 1);}
}

注意，去重判断变成了如下代码。和上面代码的区别是一个为i > 0，一个为i > startIndex。以[1,2,2]为例子，当startIndex=2时。

• 如果代码为i > 0，就会进入去重，导致子集[1,2,2]无法找到，只能找到[]、[1]、[1,2]。
• 但是如果代码为i > startIndex，不会触发去重，因为i = startIndex

// 去重
if (i > startIndex && nums[i - 1] == nums[i]) {continue;
}

递增子序列※

public List<List<Integer>> findSubsequences(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtrack(result, path, nums, 0);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int startIndex) {// 任何集合都要存储，没有说需要满足什么条件才可以存储if (path.size() >= 2) {result.add(new ArrayList<>(path));}// 用来去重HashMap<Integer, Boolean> useMap = new HashMap<>();for (int i = startIndex; i < nums.length; i++) {// 如果不是递增，continueif (path.size() > 0 && nums[i] < path.get(path.size() - 1)) {continue;}// 去重，如果前面有用过相同的元素，直接continueif (useMap.getOrDefault(nums[i], false) == true) {continue;}useMap.put(nums[i], true);path.add(nums[i]);backtrack(result, path, nums, i + 1);path.remove(path.size() - 1);}
}

如果说数据为 [1, 2, 3, 4, 1, 1] ，不去重答案就会出问题

全排列

https://leetcode.cn/problems/permutations/

这道题只能暴力求解

public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] useArr = new boolean[nums.length];backtrack(result, path, nums, useArr);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] useArr) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));}for (int i = 0; i < nums.length; i++) {if (useArr[i] == true) {continue;}useArr[i] = true;path.add(nums[i]);backtrack(result, path, nums, useArr);useArr[i] = false;path.remove(path.size() - 1);}
}

不用数组useArr来辅助也可以，直接使用path的contain方法来判断元素是否已经存在即可

这道题和前面比较大的一个区别是不再需要startIndex这个变量，而是遍历整个数组，因为需要的所有排序

全排列 II

https://leetcode.cn/problems/permutations-ii/description/

public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] useArr = new boolean[nums.length];// 升序排序Arrays.sort(nums);backtrack(result, path, nums, useArr);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] useArr) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));}for (int i = 0; i < nums.length; i++) {if (useArr[i] == true) {continue;}// 去重，如果当前元素和前一个元素相同，而且useArr[i - 1] == false，前面一个元素肯定已经被同样的方式使用过，当前组合不需要再往下遍历了if (i > 0 && nums[i - 1] == nums[i] && useArr[i - 1] == false) {continue;}useArr[i] = true;path.add(nums[i]);backtrack(result, path, nums, useArr);useArr[i] = false;path.remove(path.size() - 1);}
}

重新安排行程

https://leetcode.cn/problems/reconstruct-itinerary/description/

题意

List<List<String>> tickets 中存储了多张票的起点和终点，我们要做的是：从起点JFK开始旅行，然后把每张票使用一遍，注意每张票只能使用一次

字典排序的意思如下，例如有两个字符串 ACD 和 ABE

• 首先对比两个字符串的第一个字母，两者都是A打平手
• 然后对比两个字符串的第二个字母，第一个字符串的字母为C，第二个字符串的字母为B，因为B在字母表中的顺序更加靠前，因此排序时ABE要排在ACD前面

代码

public List<String> findItinerary(List<List<String>> tickets) {List<String> result = new ArrayList<>();List<String> path = new ArrayList<>();// 存储开始站点 及 开始站点所对应的票 索引Map<String, List<Integer>> startStationAndIndexListMap = new HashMap<>();// 填充 startStationAndIndexListMap 的数据for (int i = 0; i < tickets.size(); i++) {List<String> ticket = tickets.get(i);if (!startStationAndIndexListMap.containsKey(ticket.get(0))) {ArrayList<Integer> indexList = new ArrayList<>();indexList.add(i);startStationAndIndexListMap.put(ticket.get(0), indexList);} else {startStationAndIndexListMap.get(ticket.get(0)).add(i);}}// 将indexList按照字典序升序排序for (Map.Entry<String, List<Integer>> entry : startStationAndIndexListMap.entrySet()) {List<Integer> indexList = entry.getValue();Collections.sort(indexList, ((o1, o2) -> {return compare(tickets.get(o1).get(1), tickets.get(o2).get(1));}));}// 用来标识哪张机票已经被使用过boolean[] useArr = new boolean[tickets.size()];// 起点是固定的，添加起点path.add("JFK");backtrack(tickets, result, path, startStationAndIndexListMap, useArr, 0, "JFK");return result;
}private void backtrack(List<List<String>> tickets, List<String> result, List<String> path, Map<String, List<Integer>> startStationAndIndexListMap, boolean[] useArr, int useTicketNum, String startStation) {if (useTicketNum == tickets.size() && result.size() == 0) {// --if-- 所有机票已经用完了，存储当前路径result.addAll(path);return;}List<Integer> indexList = startStationAndIndexListMap.get(startStation);if (indexList == null) {// 当前起点站没有机票了，直接退出return;}// 遍历从当前起始站出发的机票for (int i = 0; i < indexList.size(); i++) {if (result.size() > 0) {// --if-- 因为题目要求只要字典序最小的一条路径，因此找到一个结果就可以结束整个搜索了，这里直接returnreturn;}// 机票索引Integer ticketIndex = indexList.get(i);if (useArr[ticketIndex] == true) {// --if-- 该机票已经被使用过continue;}// 去重，当前机票首站-尾站和上一张机票的相同，直接跳过即可if (i > 0 && tickets.get(indexList.get(i - 1)).get(1).equals(tickets.get(indexList.get(i)).get(1)) && useArr[indexList.get(i - 1)] == false) {continue;}// 标识当前机票已经被使用useArr[ticketIndex] = true;path.add(tickets.get(ticketIndex).get(1));backtrack(tickets, result, path, startStationAndIndexListMap, useArr, useTicketNum + 1, tickets.get(ticketIndex).get(1));path.remove(path.size() - 1);useArr[ticketIndex] = false;}
}/*** 字典排序** @param str1* @param str2* @return*/
private int compare(String str1, String str2) {for (int i = 0; i < str1.length(); i++) {int compare = Integer.compare(str1.charAt(i), str2.charAt(i));if (compare != 0) {// --if-- 当前字母没有分出胜负，继续比较下一个字母return compare;}}return 0;
}

当然**return **compare(tickets.get(o1).get(1), tickets.get(o2).get(1));可以使用

return tickets.get(o1).get(1).compareTo(tickets.get(o2).get(1));来代替

小小优化了一下，去掉path，只使用result

public List<String> findItinerary(List<List<String>> tickets) {List<String> result = new ArrayList<>();// 存储开始站点 及 开始站点所对应的票 索引Map<String, List<Integer>> startStationAndIndexListMap = new HashMap<>();// 填充 startStationAndIndexListMap 的数据for (int i = 0; i < tickets.size(); i++) {List<String> ticket = tickets.get(i);if (!startStationAndIndexListMap.containsKey(ticket.get(0))) {ArrayList<Integer> indexList = new ArrayList<>();indexList.add(i);startStationAndIndexListMap.put(ticket.get(0), indexList);} else {startStationAndIndexListMap.get(ticket.get(0)).add(i);}}// 将indexList按照字典序升序排序for (Map.Entry<String, List<Integer>> entry : startStationAndIndexListMap.entrySet()) {List<Integer> indexList = entry.getValue();Collections.sort(indexList, ((o1, o2) -> {return tickets.get(o1).get(1).compareTo(tickets.get(o2).get(1));}));}// 用来标识哪张机票已经被使用过boolean[] useArr = new boolean[tickets.size()];// 起点是固定的，添加起点result.add("JFK");backtrack(tickets, result, startStationAndIndexListMap, useArr, "JFK");return result;
}private void backtrack(List<List<String>> tickets, List<String> result,  Map<String, List<Integer>> startStationAndIndexListMap, boolean[] useArr, String startStation) {if (result.size() == tickets.size() + 1) {// --if-- 所有机票已经用完了，存储当前路径return;}List<Integer> indexList = startStationAndIndexListMap.get(startStation);if (indexList == null) {// 当前起点站没有机票了，直接退出return;}// 遍历从当前起始站出发的机票for (int i = 0; i < indexList.size(); i++) {// 机票索引Integer ticketIndex = indexList.get(i);if (useArr[ticketIndex] == true) {// --if-- 该机票已经被使用过continue;}// 去重，当前机票首站-尾站和上一张机票的相同，直接跳过即可if (i > 0 && tickets.get(indexList.get(i - 1)).get(1).equals(tickets.get(ticketIndex).get(1)) && useArr[indexList.get(i - 1)] == false) {continue;}// 标识当前机票已经被使用useArr[ticketIndex] = true;result.add(tickets.get(ticketIndex).get(1));backtrack(tickets, result, startStationAndIndexListMap, useArr, tickets.get(ticketIndex).get(1));if (result.size() == tickets.size() + 1) {// --if-- 因为题目要求只要字典序最小的一条路径，因此找到一个结果就可以结束整个搜索了，这里直接returnreturn;}result.remove(result.size() - 1);useArr[ticketIndex] = false;}
}

字典直接存储一个站可以去往哪些站点，如果选择了该站点，将其从集合中删除，回溯的时候，再将该站点加回来

int totalStationNum;public List<String> findItinerary(List<List<String>> tickets) {totalStationNum = tickets.size() + 1;List<String> result = new ArrayList<>();// 存储开始站点 及 开始站点所对应的票 索引Map<String, List<String>> startStationAndEndStationListMap = new HashMap<>();// 填充 startStationAndIndexListMap 的数据for (int i = 0; i < tickets.size(); i++) {List<String> ticket = tickets.get(i);if (!startStationAndEndStationListMap.containsKey(ticket.get(0))) {List<String> endStationList = new ArrayList<>();endStationList.add(ticket.get(1));startStationAndEndStationListMap.put(ticket.get(0), endStationList);} else {startStationAndEndStationListMap.get(ticket.get(0)).add(ticket.get(1));}}// 将indexList按照字典序升序排序for (Map.Entry<String, List<String>> entry : startStationAndEndStationListMap.entrySet()) {Collections.sort(entry.getValue(), ((o1, o2) -> {return o1.compareTo(o2);}));}// 起点是固定的，添加起点result.add("JFK");backtrack(result, startStationAndEndStationListMap, "JFK");return result;
}private boolean backtrack(List<String> result, Map<String, List<String>> startStationAndEndStationListMap, String startStation) {if (result.size() == totalStationNum) {// --if-- 所有机票已经用完了，存储当前路径return true;}List<String> endStationList = startStationAndEndStationListMap.get(startStation);if (endStationList == null) {// 当前起点站没有机票了，直接退出return false;}// 遍历从当前起始站出发的机票int i = 0;while (i < endStationList.size()) {// 目标站点String endStation = endStationList.get(i);// 去重，当前机票首站-尾站和上一张机票的相同，直接跳过即可if (i > 0 && endStation.equals(endStationList.get(i - 1))) {i++;continue;}// 去往该站点，将其从集合中删除endStationList.remove(i);result.add(endStation);if (backtrack(result, startStationAndEndStationListMap, endStation) == true) {// --if-- 因为题目要求只要字典序最小的一条路径，因此找到一个结果就可以结束整个搜索了，这里直接returnreturn true;}result.remove(result.size() - 1);endStationList.add(i, endStation);i++;}return false;
}

代码随想录的代码效率更高

N 皇后

https://leetcode.cn/problems/n-queens/description/

思路：遍历每一行，然后看当行的每列，再判断当前位置是否可行

public List<List<String>> solveNQueens(int n) {List<List<String>> result = new ArrayList<>();// 初始化棋盘char[][] chessboard = new char[n][n];for (int i = 0; i < n; i++) {Arrays.fill(chessboard[i], '.');}backtrack(result, chessboard, 0, n);return result;
}private void backtrack(List<List<String>> result, char[][] chessboard, int layer, int n) {if (layer == n) {// --for-- 遍历到最后一行了，保存结果就结束List<String> path = new ArrayList<>();for (int i = 0; i < chessboard.length; i++) {path.add(new String(chessboard[i]));}result.add(path);}for (int j = 0; j < n; j++) {// --for-- 遍历棋盘中当前行的每一列boolean isCanPlace = true;if (layer > 0) {// --if-- 如果是第二行以上，需要判断上面行有没有皇后排斥。第一行不需要看for (int i = 0; i < layer; i++) {// 判断同列是否有皇后if (chessboard[i][j] == 'Q') {isCanPlace = false;break;}// 判断斜对角是否有皇后if (((j - (layer - i)) >= 0 && chessboard[i][j - (layer - i)] == 'Q') ||(j + (layer - i) < n && chessboard[i][j + (layer - i)] == 'Q')) {isCanPlace = false;break;}}}if (isCanPlace == true) {// --if-- 当前位置可以放皇后chessboard[layer][j] = 'Q';backtrack(result, chessboard, layer + 1, n);chessboard[layer][j] = '.';}}
}

代码随想录中有更快的方法

解数独

https://leetcode.cn/problems/sudoku-solver/description/

直接遍历

一个单元格一个单元格的遍历，然后遍历[1,9]的每个数字，判断该数字是否可设置。如果所有数字都不可以设置，回溯

char[] selectNumCharArr = new char[]{'1', '2', '3', '4', '5', '6', '7', '8', '9'};
int cellRowIndex;
int cellColumnIndex;
int cellRowIndexStart;
int cellColumnIndexStart;
int cellRowIndexEnd;
int cellColumnIndexEnd;
boolean reachEnd;
boolean isFindResult;
boolean isExit;public void solveSudoku(char[][] board) {backtrack(0, 0, board);
}/*** 思路：依次遍历每一个格子来填充数字** @param rowIndex* @param columnIndex* @param board* @return*/
private boolean backtrack(int rowIndex, int columnIndex, char[][] board) {if (rowIndex == board.length) {// --if-- 所有行都已经遍历完成，说明全部数字填充完成return true;}if (board[rowIndex][columnIndex] != '.') {// --if-- 当前格子已经有数字// 判断当前行的每个格子是否遍历完成reachEnd = (columnIndex + 1 == board.length);// 如果当前行遍历完成，就要换行，columnIndex从0开始isFindResult = backtrack(reachEnd ? rowIndex + 1 : rowIndex, reachEnd ? 0 : columnIndex + 1, board);if (isFindResult) {// --if-- 找到结果，直接返回return true;}} else {for (int k = 0; k < selectNumCharArr.length; k++) {char numChar = selectNumCharArr[k];// 检测同一行是否有重复值isExit = false;for (int j = 0; j < board.length; j++) {if (board[rowIndex][j] == numChar) {isExit = true;break;}}if (isExit) {continue;}// 检测同一列是否有重复值for (int i = 0; i < board.length; i++) {if (board[i][columnIndex] == numChar) {isExit = true;break;}}if (isExit) {continue;}// 检测框里面是否有重复值cellRowIndex = rowIndex / 3;cellColumnIndex = columnIndex / 3;cellRowIndexStart = cellRowIndex * 3;cellColumnIndexStart = cellColumnIndex * 3;cellRowIndexEnd = (cellRowIndex + 1) * 3;cellColumnIndexEnd = (cellColumnIndex + 1) * 3;for (int i = cellRowIndexStart; i < cellRowIndexEnd; i++) {for (int j = cellColumnIndexStart; j < cellColumnIndexEnd; j++) {if (board[i][j] == numChar) {isExit = true;break;}}if (isExit) {break;}}if (isExit) {continue;}// 通过上述校验，可以放下当前数字board[rowIndex][columnIndex] = numChar;// 递归到下一个格子reachEnd = (columnIndex + 1 == board.length);isFindResult = backtrack(reachEnd ? rowIndex + 1 : rowIndex, reachEnd ? 0 : columnIndex + 1, board);if (isFindResult) {return true;}// 回溯board[rowIndex][columnIndex] = '.';}}return false;
}

优化

使用boolean数组去重，减少行、列、单元格的循环判断

char[] selectNumCharArr = new char[]{'1', '2', '3', '4', '5', '6', '7', '8', '9'};
boolean reachEnd;
boolean isFindResult;
// 行去重
boolean[][] rowUsedArr = new boolean[9][9];
// 列去重
boolean[][] columnUsedArr = new boolean[9][9];
// 单元去重
boolean[][] cellUsedArr = new boolean[9][9];public void solveSudoku(char[][] board) {int num;for (int i = 0; i < board.length; i++) {for (int j = 0; j < board.length; j++) {if (board[i][j] != '.') {num = board[i][j] - '1';rowUsedArr[i][num] = true;columnUsedArr[j][num] = true;cellUsedArr[(i / 3) * 3 + (j / 3)][num] = true;}}}backtrack(0, 0, board);
}/*** 思路：依次遍历每一个格子来填充数字** @param rowIndex* @param columnIndex* @param board* @return*/
private boolean backtrack(int rowIndex, int columnIndex, char[][] board) {if (rowIndex == board.length) {// --if-- 所有行都已经遍历完成，说明全部数字填充完成return true;}if (board[rowIndex][columnIndex] != '.') {// --if-- 当前格子已经有数字// 判断当前行的每个格子是否遍历完成reachEnd = (columnIndex + 1 == board.length);// 如果当前行遍历完成，就要换行，columnIndex从0开始isFindResult = backtrack(reachEnd ? rowIndex + 1 : rowIndex, reachEnd ? 0 : columnIndex + 1, board);if (isFindResult) {// --if-- 找到结果，直接返回return true;}} else {for (int k = 0; k < selectNumCharArr.length; k++) {int num = selectNumCharArr[k] - '1';// 检测同一行是否有重复值if (rowUsedArr[rowIndex][num]) {continue;}// 检测同一列是否有重复值if (columnUsedArr[columnIndex][num] == true) {continue;}// 检测框里面是否有重复值int cellIndex = (rowIndex / 3) * 3 + (columnIndex / 3);if (cellUsedArr[cellIndex][num]) {continue;}// 通过上述校验，可以放下当前数字board[rowIndex][columnIndex] = selectNumCharArr[k];rowUsedArr[rowIndex][num] = true;columnUsedArr[columnIndex][num] = true;cellUsedArr[cellIndex][num] = true;// 递归到下一个格子reachEnd = (columnIndex + 1 == board.length);isFindResult = backtrack(reachEnd ? rowIndex + 1 : rowIndex, reachEnd ? 0 : columnIndex + 1, board);if (isFindResult) {return true;}// 回溯board[rowIndex][columnIndex] = '.';rowUsedArr[rowIndex][num] = false;columnUsedArr[columnIndex][num] = false;cellUsedArr[cellIndex][num] = false;}}return false;
}