回溯算法
数据结构和算法
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。
回溯是递归的副产品，只要有递归就会有回溯。回溯函数也就是递归函数，指的都是一个函数。
回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序，排列有序，就可以了。
所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
#回溯法模板
回溯三部曲。
- 回溯函数模板返回值以及参数
- 回溯函数终止条件
- 回溯搜索的遍历过程
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//横向遍历,一个节点有多少个孩子，这个for循环就执行多少次。
处理节点;
backtracking(路径，选择列表); // 递归,纵向遍历
回溯，撤销处理结果
}
}
51八皇后问题:（回溯算法）
- 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法（92）如
{0 , 4, 7, 5, 2, 6, 1, 3} - 思路
- 1 第一个皇后先放第一行第一列
- 2 第二个皇后放在第二行第一列、然后判断是否冲突， 如果冲突，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
- 3 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
- 4 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
- 5 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤
- 用一个一维数组存放结果，因为任意两个皇后是不可能存在同一行的情况。只需记录皇后在棋盘中的列坐标即可。一维数组的索引表示皇后在棋盘中的横坐标，数组所对应的值表示皇后在棋盘中的列坐标。
public class Queue8 {
int max = 8;
int[] array = new int[max];
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.printf("一共有%d解法", count);
System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w
}
//check是每一次递归时，进入到check中都有for(int i=0; i< max;i++)，因此会有回溯(检查之前的对不对)
private void check(int n) {//编写一个方法，放置第n个皇后
if(n == max) { //n = 8 , 其实8个皇后就既然放好
print();
return;
}
for(int i = 0; i < max; i++) {//依次放入皇后，并判断是否冲突
array[n] = i;//先把当前这个皇后 n , 放到该行的第1列
if(judge(n)) { // 不冲突 判断当放置第n个皇后到i列时，是否冲突
check(n+1); //接着放n+1个皇后,即开始递归
}
//如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得后移的一个位置
}
}
//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
private boolean judge(int n) {
judgeCount++;
for(int i = 0; i < n; i++) {
//1. array[i] == array[n] 判断纵坐标是否相等
//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 判断横纵坐标是否相等
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
return false;
}
}
return true;
}
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
77组合及剪枝优化
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：输入：n = 4, k = 2
输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
示例 2：输入：n = 1, k = 1 输出：[[1]]
把组合问题抽象为如下树形结构：
一开始集合是 1，2，3，4， 从左向右取数，取过的数，不再重复取。
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
其中，n相当于树的宽度，k相当于树的深度。只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
- 剪枝优化：如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
- 已经选择的元素个数：path.size();
- 所需需要的元素个数为: k - path.size();
- 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
- 在集合n中至多要从该起始位置 : i <= 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]。
如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合(opens new window)
注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我在讲解排列的时候会重点介绍。
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;i++)
//startIndex有无取决于集合之间有无影响
//i还是i+1取决于是否重复选择
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
path.add(i);
combineHelper(n, k, i + 1);//不重复则需要
path.removeLast();
}
}
}
17电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：输入：digits = "" 输出：[]
示例 3：输入：digits = "2" 输出：["a","b","c"]
时间复杂度：O(3^m*4^n)，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3^m × 4^n种，需要遍历每一种字母组合。
空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。
class Solution {
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);//删除index回溯
}
}
}
}
216组合总和III√
找出所有相加之和为 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]]
多了求和条件
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;
}
}
}
39组合总和√
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
示例 2：输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：输入: candidates = [2], target = 1 输出: []
特点：1，组合没有数量要求2，元素可无限重复选取
时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 O(n×2^n) 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 target−candidates[idx]≥0 进行剪枝，所以实际运行情况是远远小于这个上界的。
空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。
// 剪枝优化
//组合没有数量要求,元素可无限重复选取
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);// 关键点:不用i+1了，表示可以重复读取当前的数
path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
}
}
}
40组合总和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]]
本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而39.组合总和是无重复元素的数组candidates
集合（数组candidates）有重复元素，但还不能有重复的组合。
树层去重的话，需要对数组排序！
要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。也就是说递归无需去重，而for循环去重
在candidates[i] == candidates[i - 1]相同的情况下：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过，说明是进入下一层递归，去下一个数，所以是树枝上
used[i - 1] == false，说明同一树层candidates[i - 1]使用过，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
sum + candidates[i] <= target为剪枝操作
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
boolean[] used;
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
// 加标志数组，用来辅助判断同层节点是否已经遍历
Arrays.fill(used, false);
// 为了将重复的数字都放到一起，所以先进行排序
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return ans;
}
private void backTracking(int[] candidates, int target, int startIndex) {
if (sum == target) {
ans.add(new ArrayList(path));
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {//,剪枝操作
break;
}
// 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
sum += candidates[i];
path.add(candidates[i]);
// 每个节点仅能选择一次，所以从下一位开始
backTracking(candidates, target, i + 1);
used[i] = false;
sum -= candidates[i];
path.removeLast();
}
}
}
131分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1：输入：s = "aab"输出：[["a","a","b"],["aa","b"]]
示例 2：输入：s = "a" 输出：[["a"]]
关键
切割问题，有不同的切割方式
判断回文
切割问题类似组合问题。
例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。
切割问题，也可以抽象为一棵树形结构
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
处理组合递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。如果起始位置已经大于s的大小，说明已经找到了一组分割方案了，[startIndex, i] 就是要截取的子串
时间复杂度：O(n⋅2^n)，其中 n 是字符串 s 的长度。在最坏情况下，s 包含 n 个完全相同的字符，因此它的任意一种划分方法都满足要求。而长度为 n 的字符串的划分方案数为 2^n−1=O(2^n)，每一种划分方法需要 O(n) 的时间求出对应的划分结果并放入答案，因此总时间复杂度为 O(n⋅2^n)。尽管动态规划预处理需要 O(n^2) 的时间，但在渐进意义下小于 O(n⋅2^n)，因此可以忽略。
空间复杂度：O(n^2)，这里不计算返回答案占用的空间。数组 f 需要使用的空间为 O(n^2)，而在回溯的过程中，我们需要使用 O(n) 的栈空间以及 O(n) 的用来存储当前字符串分割方法的空间。由于 O(n) 在渐进意义下小于 O(n^2)，因此空间复杂度为 O(n^2)。
class Solution {
//保持前几题一贯的格式， initialization
List<List<String>> res = new ArrayList<>();
List<String> cur = new ArrayList<>();
public List<List<String>> partition(String s) {
backtracking(s, 0, new StringBuilder());
return res;
}
private void backtracking(String s, int start, StringBuilder sb){
//因为是起始位置一个一个加的，所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文，所以cur是满足条件的
if (start == s.length()){
//注意创建一个新的copy
res.add(new ArrayList<>(cur));
return;
}
//像前两题一样从前往后搜索，如果发现回文，进入backtracking,起始位置后移一位，循环结束照例移除cur的末位
for (int i = start; i < s.length(); i++){
sb.append(s.charAt(i));
if (check(sb)){
cur.add(sb.toString());
backtracking(s, i + 1, new StringBuilder());//切割过的地方不能重复切割所以递归函数需要传入i + 1。
cur.remove(cur.size() -1 );
}
}
}
//helper method, 检查是否是回文
private boolean check(StringBuilder sb){
for (int i = 0; i < sb.length()/ 2; i++){
if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}
}
return true;
}
}
93复原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"]
0 <= s.length <= 3000
s 仅由数字组成
//方法一：但使用stringBuilder，故优化时间、空间复杂度，因为向字符串插入字符时无需复制整个字符串，从而减少了操作的时间复杂度，也不用开新空间存subString，从而减少了空间复杂度。
class Solution {
List<String> result = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
backTracking(sb, 0, 0);
return result;
}
private void backTracking(StringBuilder s, int startIndex, int dotCount){
if(dotCount == 3){
if(isValid(s, startIndex, s.length() - 1)){
result.add(s.toString());
}
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isValid(s, startIndex, i)){
s.insert(i + 1, '.');
backTracking(s, i + 2, dotCount + 1);
s.deleteCharAt(i + 1);
}else{
break;
}
}
}
//[start, end]
private boolean isValid(StringBuilder s, int start, int end){
if(start > end)
return false;
if(s.charAt(start) == '0' && start != end)
return false;
int num = 0;
for(int i = start; i <= end; i++){
int digit = s.charAt(i) - '0';
num = num * 10 + digit;
if(num > 255)
return false;
}
return true;
}
}
78子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：输入：nums = [0]输出：[[],[0]]
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合
时间复杂度：O(n*2^n)。一共 2^n个状态，每种状态需要 O(n) 的时间来构造子集。
空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
public List<List<Integer>> subsets(int[] nums) {
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();
}
}
}
90子集II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
集合里有重复元素了，而且求取的子集要去重。
排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums.length == 0){
result.add(path);
return result;
}
Arrays.sort(nums);
used = new boolean[nums.length];
subsetsWithDupHelper(nums, 0);
return result;
}
private void subsetsWithDupHelper(int[] nums, int startIndex){
result.add(new ArrayList<>(path));
if (startIndex >= nums.length){
return;
}
for (int i = startIndex; i < nums.length; i++){
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
path.add(nums[i]);
used[i] = true;
subsetsWithDupHelper(nums, i + 1);
path.removeLast();
used[i] = false;
}
}
}
491.递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况
在90.子集II (opens new window)中我们是通过排序，再加一个标记数组来达到去重的目的。
而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑！
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int startIndex){
if(path.size() >= 2)
result.add(new ArrayList<>(path));
HashSet<Integer> hs = new HashSet<>();
for(int i = startIndex; i < nums.length; i++){
if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))
continue;
hs.add(nums[i]);
path.add(nums[i]);
backTracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
46全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：输入：nums = [1] 输出：[[1]]
时间复杂度：O(n * n!)，n! 表示所有可能的排列数，而每次排列生成的时间复杂度为 O(n)。
空间复杂度：O(n)，由于递归的深度为 n，栈空间消耗为 O(n)。
每层都是从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;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
47.全排列 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;
}
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;//回溯
}
}
}
}
332重新安排行程
给定一个机票的字符串二维数组 [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"]。但是它自然排序更大更靠后。
深搜+回溯，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。
这道题目有几个难点：
一个行程中，如果航班处理不好容易变成一个圈，成为死循环
有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
搜索的过程中，如何遍历一个机场所对应的所有机场。
class Solution {
private LinkedList<String> res;
private LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
path.add("JFK");
boolean[] used = new boolean[tickets.size()];
backTracking((ArrayList) tickets, used);
return res;
}
public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
if (path.size() == tickets.size() + 1) {
res = new LinkedList(path);
return true;
}
for (int i = 0; i < tickets.size(); i++) {
if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
path.add(tickets.get(i).get(1));
used[i] = true;
if (backTracking(tickets, used)) {
return true;
}
used[i] = false;
path.removeLast();
}
}
return false;
}
}
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：输入：n = 1
输出：["()"]
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
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);
}
}
}
79单词搜索
给定一个 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
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
class Solution {
public boolean exist(char[][] board, String word) {
int h = board.length, w = board[0].length;
boolean[][] visited = new boolean[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
if (board[i][j] != s.charAt(k)) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean result = false;
for (int[] dir : directions) {
int newi = i + dir[0], newj = j + dir[1];
//保证不越界
if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
if (!visited[newi][newj]) {
//递归判断满足条件
boolean flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;//在递归返回上一级调用时，取消当前路径对 i, j 位置的标记，允许其他路径再次访问这个单元格。
return result;
}
}
51N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
时间复杂度：O(N!)，其中 N 是皇后数量。
空间复杂度：O(N)，其中 N 是皇后数量。由于使用位运算表示，因此存储皇后信息的空间复杂度是 O(1)，空间复杂度主要取决于递归调用层数和记录每行放置的皇后的列下标的数组，递归调用层数不会超过 N，数组的长度为 N。
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;
}
}
37解数独
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
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;
}
}