什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯法的效率
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
组合是不强调元素顺序的，排列是强调元素顺序
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯法模板
回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
组合问题1
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
回溯法三部曲
- 递归函数的返回值以及参数
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
代码如下：
List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 用来存放符合条件结果
其实不定义这两个全局遍历也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以我定义全局变量了。
函数里一定有两个参数，既然是集合n里面取k的数，那么n和k是两个int型的参数。
然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
为什么要有这个startIndex呢？
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。
所以需要startIndex来记录下一层递归，搜索的起始位置。
- 回溯函数终止条件
什么时候到达所谓的叶子节点了呢？
path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
此时用result二维数组，把path保存起来，并终止本层递归。
所以终止条件代码如下：
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
- 单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
代码如下：
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
path.add(i); // 处理节点
backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
path.removeLast(); // 回溯，撤销处理的节点
}
可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
剪枝优化
回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。
来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。
这么说有点抽象，如图所示：
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
接下来看一下优化过程如下：
- 已经选择的元素个数：path.size();
- 还需要的元素个数为: k - path.size();
- 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。
所以优化之后的for循环是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
完整代码
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
combineHelper(n, k, 1);
return result;
}
/**
* 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
* @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
*/
private void combineHelper(int n, int k, int startIndex){
//终止条件
if (path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
path.add(i);
combineHelper(n, k, i + 1);
path.removeLast();
}
}
}
组合问题2
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,…,9]。
已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return result;
}
private void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝
if (sum > targetSum) {
return;
}
if (path.size() == k) {
if (sum == targetSum) result.add(new ArrayList<>(path));
return;
}
// 减枝 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
//回溯
path.removeLast();
//回溯
sum -= i;
}
}
}
组合电话号码的字母
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例: 输入：”23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
思路
- 数字和字母如何映射
- 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
- 输入1 * #按键等等异常情况
数字和字母如何映射
可以使用map或者定义一个二维数组，例如：string letterMap[10]，来做映射，我这里定义一个二维数组，代码如下：
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
例如：输入：”23”，抽象为树形结构，如图所示：
class Solution {
//设置全局列表存储最后的结果
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;
}
//每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
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));
//c
backTracking(digits, numString, num + 1);
//剔除末尾的继续尝试
temp.deleteCharAt(temp.length() - 1);
}
}
}
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
如图：
本题和之前有两点不同：
- 组合没有数量要求
- 元素可无限重复选取
// 剪枝优化
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 先进行排序
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就终止遍历
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
}
}
}
组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。
示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：
- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
int sum = 0;
public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
//为了将重复的数字都放到一起，所以先进行排序
Arrays.sort( candidates );
backTracking( candidates, target, 0 );
return res;
}
private void backTracking( int[] candidates, int target, int start ) {
if ( sum == target ) {
res.add( new ArrayList<>( path ) );
return;
}
for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
//正确剔除重复解的办法
//跳过同一树层使用过的元素
if ( i > start && candidates[i] == candidates[i - 1] ) {
continue;
}
sum += candidates[i];
path.add( candidates[i] );
// i+1 代表当前组内元素只选取一次
backTracking( candidates, target, i + 1 );
int temp = path.getLast();
sum -= temp;
path.removeLast();
}
}
}
分割回文串问题
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,”b”], [“a”,”a”,”b”] ]
思路
关于本题，大家也可以看我在B站的视频讲解：131.分割回文串（B站视频）(opens new window)
本题这涉及到两个关键问题：
- 切割问题，有不同的切割方式
- 判断回文
如：切割过的地方不能重复切割所以递归函数需要传入i + 1。
class Solution {
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;
}
}
分割之复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 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 地址。
示例 1：
- 输入：s = “25525511135”
- 输出：[“255.255.11.135”,”255.255.111.35”]
示例 2：
- 输入：s = “0000”
- 输出：[“0.0.0.0”]
示例 3：
- 输入：s = “1111”
- 输出：[“1.1.1.1”]
示例 4：
- 输入：s = “010010”
- 输出：[“0.10.0.10”,”0.100.1.0”]
示例 5：
- 输入：s = “101023”
- 输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
提示：
- 0 <= s.length <= 3000
- s 仅由数字组成
思路
判断子串是否合法
最后就是在写一个判断段位是否是有效段位了。
主要考虑到如下三点：
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
class Solution {
List<String> result = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if (s.length() > 12) return result; // 算是剪枝了
backTrack(s, 0, 0);
return result;
}
// startIndex: 搜索的起始位置， pointNum:添加逗点的数量
private void backTrack(String s, int startIndex, int pointNum) {
if (pointNum == 3) {// 逗点数量为3时，分隔结束
// 判断第四段⼦字符串是否合法，如果合法就放进result中
if (isValid(s,startIndex,s.length()-1)) {
result.add(s);
}
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isValid(s, startIndex, i)) {
s = s.substring(0, i + 1) + "." + s.substring(i + 1); //在str的后⾯插⼊⼀个逗点
pointNum++;
backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
pointNum--;// 回溯
s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
} else {
break;
}
}
}
// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
private Boolean isValid(String s, int start, int end) {
if (start > end) {
return false;
}
if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
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;
}
}
//方法二：比上面的方法时间复杂度低，更好地剪枝，优化时间复杂度
class Solution {
List<String> result = new ArrayList<String>();
StringBuilder stringBuilder = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
restoreIpAddressesHandler(s, 0, 0);
return result;
}
// number表示stringbuilder中ip段的数量
public void restoreIpAddressesHandler(String s, int start, int number) {
// 如果start等于s的长度并且ip段的数量是4，则加入结果集，并返回
if (start == s.length() && number == 4) {
result.add(stringBuilder.toString());
return;
}
// 如果start等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是start小于s的长度，则直接返回
if (start == s.length() || number == 4) {
return;
}
// 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0
&& Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) {
// 如果ip段的长度大于1，并且第一位为0的话，continue
if (i + 1 - start > 1 && s.charAt(start) - '0' == 0) {
continue;
}
stringBuilder.append(s.substring(start, i + 1));
// 当stringBuilder里的网段数量小于3时，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点
if (number < 3) {
stringBuilder.append(".");
}
number++;
restoreIpAddressesHandler(s, i + 1, number);
number--;
// 删除当前stringBuilder最后一个网段，注意考虑点的数量的问题
stringBuilder.delete(start + number, i + number + 2);
}
}
}
子集1
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
class Solution {
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();
}
}
}
子集II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路
后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。
（注意去重需要先对集合排序）
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsetsWithDup( int[] nums ) {
Arrays.sort( nums );
subsetsWithDupHelper( nums, 0 );
return res;
}
private void subsetsWithDupHelper( int[] nums, int start ) {
res.add( new ArrayList<>( path ) );
for ( int i = start; i < nums.length; i++ ) {
// 跳过当前树层使用过的、相同的元素
if ( i > start && nums[i - 1] == nums[i] ) {
continue;
}
path.add( nums[i] );
subsetsWithDupHelper( nums, i + 1 );
path.removeLast();
}
}
}
递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
- 输入: [4, 6, 7, 7]
- 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
- 给定数组的长度不会超过15。
- 数组中的整数范围是 [-100,100]。
- 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况
本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了。
所以不能使用之前的去重逻辑！
本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。
为了有鲜明的对比，我用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：
同一父节点下的同层上使用过的元素就不能在使用了
Map.getOrDefault(key，默认值)；
Map中会存储一一对应的key和value。
如果 在Map中存在key，则返回key所对应的的value。
如果 在Map中不存在key，则返回默认值。
class Solution {
//结果集合
List<List<Integer>> res = new ArrayList<>();
//路径集合
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
getSubsequences(nums,0);
return res;
}
private void getSubsequences( int[] nums, int start ) {
if(path.size()>1 ){
res.add( new ArrayList<>(path) );
// 注意这里不要加return，要取树上的节点
}
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=start ;i < nums.length ;i++){
if(!path.isEmpty() && nums[i]< path.getLast()){
continue;//跳过当前步，进入下一步，还在当前循环中
}
// 使用过了当前数字
if ( map.getOrDefault( nums[i],0 ) >=1 ){
continue;
}
map.put(nums[i],map.getOrDefault( nums[i],0 )+1);
path.add( nums[i] );
getSubsequences( 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] ]
排列问题的不同：
- 每层都是从0开始搜索而不是startIndex
- 需要used数组记录path里都放了哪些元素了
class Solution {
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;
}
// 写法二：如果path中已有，则跳过
//if (path.contains(nums[i])) {
// continue;
//}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
全排列 II
给定一个可包含重复数字的序列 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[i] <= 10
给定一个可包含重复数字的序列，要返回所有不重复的全排列。这里又涉及到去重了。
还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
class Solution {
//存放结果
List<List<Integer>> result = new ArrayList<>();
//暂存结果
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
backTrack(nums, used);
return result;
}
private void backTrack(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
//方式二：HashSet<Integer> hashSet = new HashSet<>();//层去重
for (int i = 0; i < nums.length; i++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
//如果同⼀树⽀nums[i]没使⽤过开始处理
if (used[i] == false) {
used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
path.add(nums[i]);
backTrack(nums, used);
path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
used[i] = false;//回溯
}
}
}
}
重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
提示：
- 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
- 所有的机场都用三个大写字母表示（机场代码）。
- 假定所有机票至少存在一种合理的行程。
- 所有的机票必须都用一次 且 只能用一次。
示例 1：
- 输入：[[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
- 输出：[“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]
示例 2：
- 输入：[[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
- 输出：[“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
- 解释：另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]。，但是它字典排序更大更靠后。
提示：
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi
class Solution {
private Deque<String> res;
private Map<String, Map<String, Integer>> map;
private boolean backTracking(int ticketNum){
if(res.size() == ticketNum + 1){
return true;
}
String last = res.getLast();
if(map.containsKey(last)){//防止出现null
for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
int count = target.getValue();
if(count > 0){
res.add(target.getKey());
target.setValue(count - 1);
if(backTracking(ticketNum)) return true;
res.removeLast();
target.setValue(count);
}
}
}
return false;
}
public List<String> findItinerary(List<List<String>> tickets) {
map = new HashMap<String, Map<String, Integer>>();
res = new LinkedList<>();
for(List<String> t : tickets){
Map<String, Integer> temp;
if(map.containsKey(t.get(0))){
temp = map.get(t.get(0));
temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
}else{
temp = new TreeMap<>();//升序Map
temp.put(t.get(1), 1);
}
map.put(t.get(0), temp);
}
res.add("JFK");
backTracking(tickets.size());
return new ArrayList<>(res);
}
}
N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
- 输入：n = 4
- 输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
- 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
- 输入：n = 1
- 输出：[[“Q”]]
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
backTrack(n, 0, chessboard);
return res;
}
public void backTrack(int n, int row, char[][] chessboard) {
if (row == n) {
res.add(Array2List(chessboard));
return;
}
for (int col = 0;col < n; ++col) {
if (isValid (row, col, n, chessboard)) {
chessboard[row][col] = 'Q';
backTrack(n, row+1, chessboard);
chessboard[row][col] = '.';
}
}
}
public List Array2List(char[][] chessboard) {
List<String> list = new ArrayList<>();
for (char[] c : chessboard) {
list.add(String.copyValueOf(c));
}
return list;
}
public boolean isValid(int row, int col, int n, char[][] chessboard) {
// 检查列
for (int i=0; i<row; ++i) { // 相当于剪枝
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查45度对角线
for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查135度对角线
for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
解数独
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。
一个数独。
答案被标成红色。
提示：
- 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的
board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
N皇后问题 是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHelper(board);
}
private boolean solveSudokuHelper(char[][] board){
//「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
// 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
for (int i = 0; i < 9; i++){ // 遍历行
for (int j = 0; j < 9; j++){ // 遍历列
if (board[i][j] != '.'){ // 跳过原始数字
continue;
}
for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
if (isValidSudoku(i, j, k, board)){
board[i][j] = k;
if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
return true;
}
board[i][j] = '.';
}
}
// 9个数都试完了，都不行，那么就返回false
return false;
// 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
// 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
}
}
// 遍历完没有返回false，说明找到了合适棋盘位置了
return true;
}
/**
* 判断棋盘是否合法有如下三个维度:
* 同行是否重复
* 同列是否重复
* 9宫格里是否重复
*/
private boolean isValidSudoku(int row, int col, char val, char[][] board){
// 同行是否重复
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
// 同列是否重复
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
子集问题分析：
- 时间复杂度：$O(n × 2^n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2^n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$。
- 空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$。
排列问题分析：
- 时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ….. 1 = n!。每个叶子节点都会有一个构造全排列填进数组的操作（对应的代码：
result.push_back(path)），该操作的复杂度为$O(n)$。所以，最终时间复杂度为：n * n!，简化为$O(n!)$。 - 空间复杂度：$O(n)$，和子集问题同理。
组合问题分析：
- 时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
- 空间复杂度：$O(n)$，和子集问题同理。
N皇后问题分析：
- 时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * …. * 1。
- 空间复杂度：O(n)，和子集问题同理。
解数独问题分析：
- 时间复杂度：O(9^m) , m是’.’的数目。
- 空间复杂度：O(n^2)，递归的深度是n^2
