1、概念
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
2、基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
3、用回溯法解题的一般步骤：
（1）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
4、算法框架
（1）问题框架
设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。
（2）非递归回溯框架
1: int a[n],i;
2: 初始化数组a[];
3: i = 1;
4: while (i>0(有路可走) and (未达到目标)) // 还未回溯到头
5: {
6: if(i > n) // 搜索到叶结点
7: {
8: 搜索到一个解，输出；
9: }
10: else // 处理第i个元素
11: {
12: a[i]第一个可能的值；
13: while(a[i]在不满足约束条件且在搜索空间内)
14: {
15: a[i]下一个可能的值；
16: }
17: if(a[i]在搜索空间内)
18: {
19: 标识占用的资源；
20: i = i+1; // 扩展下一个结点
21: }
22: else
23: {
24: 清理所占的状态空间； // 回溯
25: i = i –1;
26: }
27: }
（3）递归的算法框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
1: int a[n];
2: try(int i)
3: {
4: if(i>n)
5: 输出结果;
6: else
7: {
8: for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
9: {
10: if(fun(j)) // 满足限界函数和约束条件
11: {
12: a[i] = j;
13: ... // 其他操作
14: try(i+1);
15: 回溯前的清理工作（如a[i]置空值等）;
16: }
17: }
18: }
19: }
应用
8皇后：
void queen(int row){
if(row==n)
total++;
else
for(int col=0;col!=n;col++){
c[row]=col;
if(is_ok(row))
queen(row+1);
}
}
算法是逐行安排皇后的，其参数row为现在正执行到第几行。n是皇后数，在八皇后问题里当然就是8啦。
第2行好理解，如果程序当前能正常执行到第8行，那自然是找到了一种解法，于是八皇后问题解法数加1。
如果当前还没排到第八行，则进入else语句。遍历所有列col，将当前col存储在数组c里，然后使用is_ok()检查row行col列能不能摆皇后，若能摆皇后，则递归调用queen去安排下一列摆皇后的问题。
#include<iostream>
#include<math.h>
using namespace std;
int n=8;
int total=0;
int *c=new int(n);
bool is_ok(int row){
for(int j=0;j!=row;j++){
if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])
return false;
}
return true;
}
void queen(int row){
if(row==n)
total++;
else
for(int col=0;col!=n;col++){
c[row]=col;
if(is_ok(row))
queen(row+1);
}
}
int main(){
queen(0);
cout<<total;
return 1;
}
非递归实现
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<vector>
#include<unordered_map>
#include<stack>
#include<sstream>
#include<unordered_set>
using namespace std;
int x[9];
bool place(int k) {
for (int i = 1; i < k; i++) {
if (x[i] == x[k] || abs(x[i] - x[k]) == abs(i - k)) {
//cout << "hhh " << x[i] << " " << x[k] << " " << i << " " << k << endl;
return false;
}
}
return true;
}
int h;
void nqueens1(int n) {
h = 0;
int i, k;
for (i = 1; i <= n; i++)
x[i] = 0;
k = 1;
while (k >= 1)
{
x[k] = x[k] + 1; //在下一列放置第k个皇后
while (x[k] <= n && !place(k))
x[k] = x[k] + 1;//搜索下一列
if (x[k] <= n && k == n)//得到一个输出
{
//for(i=1;i<=n;i++)
// printf("%d ",x[i]);
//printf("\n");
cout << h++ << endl;
}
else if (x[k] <= n && k<n)
k = k + 1;//放置下一个皇后
else//x[k]>n;
{
x[k] = 0;//重置x[k],回溯
k = k - 1;
}
}
}
int main() {
nqueens1(8);
return 0;
}
递归版
#include<iostream>
#include<math.h>
using namespace std;
int n = 8;
int total = 0;
int *c = new int(n);
bool is_ok(int row) {
for (int j = 0; j != row; j++) {
if (c[row] == c[j] || row - c[row] == j - c[j] || row + c[row] == j + c[j])
return false;
}
return true;
}
void queen(int row) {
if (row == n)
total++;
else
for (int col = 0; col != n; col++) {
c[row] = col;
if (is_ok(row))
queen(row + 1);
}
}
int main() {
queen(0);
cout << total;
return 1;
}
子集subsets问题
无重复
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(nums, start, tempList: List[int], res):
res.append(tempList.copy())
for i in range(start, len(nums)):
tempList.append(nums[i])
backtrack(nums, i + 1, tempList, res)
tempList.pop()
return
backtrack(nums, 0, [], res)
print(res)
return res
有重复
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
这个注意是有duplicate的，所以要注意
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums, start, tempList: List[int], res):
res.append(tempList.copy())
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue
tempList.append(nums[i])
backtrack(nums, i + 1, tempList, res)
tempList.pop()
return
nums.sort()
res = []
backtrack(nums, 0, [], res)
print(res)
return res
也可以设置visit数组
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
continue;
}
tempSubset.add(nums[i]);
hasVisited[i] = true;
backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
hasVisited[i] = false;
tempSubset.remove(tempSubset.size() - 1);
}
}
排列permutations问题
非duplicate
这里注意是begin+1,而不是i+1
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
permuteRecursive(num, 0, result);
return result;
}
// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result) {
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}
for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
// reset
swap(num[begin], num[i]);
}
}
};
设置visit数组：
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList)); // 重新构造一个 List
return;
}
for (int i = 0; i < visited.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
有重复的
[1,1,2] have the following unique permutations:
[[1,1,2], [1,2,1], [2,1,1]]
数组元素可能含有相同的元素，进行排列时就有可能出现重复的排列，要求重复的排列只返回一个。
为什么这里排列需要一个visit数组而不能用nums[i]==nums[i-1]去重，因为swap会打乱之前排序。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(start):
if start >= len(nums):
res.append(nums.copy())
return
s = set()
for i in range(start, len(nums)):
if nums[i] in s:
continue
else:
s.add(nums[i])
nums[i], nums[start] = nums[start], nums[i]
backtrack(start + 1)
nums[i], nums[start] = nums[start], nums[i]
nums.sort()
backtrack(0)
print(res)
return res
也可以S排序，比较S[k]==S[k-1]，这种必须在不用swap的情况下
class Solution:
def permutation(self, S: str) -> List[str]:
ans = []
n = len(S)
import collections
visit = collections.defaultdict(bool)
S = sorted(S)
def backtrack(i, cur=[]):
nonlocal visit, ans
if i == n:
ans.append("".join(cur))
return
# used = collections.defaultdict(bool)
for k in range(n):
if visit[k] or (k>0 and not visit[k-1] and S[k]==S[k-1]):
continue
# if used[S[k]]:
# continue
# used[S[k]] = True
visit[k] = True
cur.append(S[k])
backtrack(i + 1, cur)
cur.pop()
visit[k] = False
backtrack(0, [])
return ans
组合
组合结果
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> combineList = new ArrayList<>();
backtracking(combineList, combinations, 1, k, n);
return combinations;
}
private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
if (k == 0) {
combinations.add(new ArrayList<>(combineList));
return;
}
for (int i = start; i <= n - k + 1; i++) { // 剪枝
combineList.add(i);
backtracking(combineList, combinations, i + 1, k - 1, n);
combineList.remove(combineList.size() - 1);
}
}
组合求和
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}
含有相同元素的求组合求和
40. Combination Sum II (Medium)
public List<List<Integer>> combinationSum2(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
1-9 数字的组合求和
216. Combination Sum III (Medium)
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
从 1-9 数字中选出 k 个数不重复的数，使得它们的和为 n。
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtracking(k, n, 1, path, combinations);
return combinations;
}
private void backtracking(int k, int n, int start,
List<Integer> tempCombination, List<List<Integer>> combinations) {
if (k == 0 && n == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
if (k == 0 || n == 0) {
return;
}
for (int i = start; i <= 9; i++) {
tempCombination.add(i);
backtracking(k - 1, n - i, i + 1, tempCombination, combinations);
tempCombination.remove(tempCombination.size() - 1);
}
}
Palindrome Partitioning
把字符串s切成很多个回文字符串
class Solution:
def partition(self, s: str) -> List[List[str]]:
def isP(x):
return x == x[-1::-1]
res = []
def backtrack(tempList, start):
if start >= len(s):
res.append(tempList.copy())
return
for i in range(start, len(s)):
if isP(s[start:i+1]):
tempList.append(s[start:i+1])
backtrack(tempList, i + 1)
tempList.pop()
backtrack([], 0)
print(res)
return res
下一个排列
逆向找一第一个小于后面值得元素，然后它和后面的大于5它的最小元素交换。 后半部分再升序即可(翻转就行)
My idea is for an array:
Start from its last element, traverse backward to find the first one with index i that satisfy num[i-1] < num[i]. So, elements from num[i] to num[n-1] is reversely sorted.
To find the next permutation, we have to swap some numbers at different positions, to minimize the increased amount, we have to make the highest changed position as high as possible. Notice that index larger than or equal to i is not possible as num[i,n-1] is reversely sorted. So, we want to increase the number at index i-1, clearly, swap it with the smallest number between num[i,n-1] that is larger than num[i-1]. For example, original number is 121543321, we want to swap the ‘1’ at position 2 with ‘2’ at position 7.
The last step is to make the remaining higher position part as small as possible, we just have to reversely sort the num[i,n-1]
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int k = n - 1;
while (k > 0 && nums[k] <= nums[k - 1]) {
k--;
}
if (k == 0) {
reverse(nums.begin(), nums.end());
return;
}
k--;
int index,t = INT_MAX;
for (int i = k + 1; i < n; i++) {
if (nums[i] > nums[k]) {
if (nums[i] < t) {
t = nums[i];
index = i;
}
}
}
swap(nums[k], nums[index]);
reverse(nums.begin() + index, nums.end());
}
};
迷路机器人
设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
这个不是在for里进行标记，是在for之前进行标记处理。
class Solution:
def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
if not obstacleGrid:
return []
m, n = len(obstacleGrid), len(obstacleGrid[0])
import collections
visit = collections.defaultdict(bool)
directions = (-1, 0, 1, 0, -1)
path = []
ans = []
def backtrack(i, j):
nonlocal path, visit, ans
key = (i, j)
if (not (0 <= i < m and 0 <= j < n)) or obstacleGrid[i][j] == 1 or visit[key]:
return False
if i == m - 1 and j == n - 1:
path.append([i, j])
ans = list(path)
return True
visit[key] = True
path.append([i, j])
if backtrack(i + 1, j) or backtrack(i, j + 1):
return True
path.pop()
# visit[key] = False
return False
if backtrack(0,0):
return ans
else:
return []
矩阵中找包含字符串的路径
输入一个字符串，打印出该字符串中字符的所有排列
class Solution:
def permutation(self, s: str) -> List[str]:
ans = []
from collections import defaultdict
visit = defaultdict(bool)
def f(temp):
if len(temp) == len(s):
nonlocal ans
ans.append("".join(temp))
return
sameMark = set()
for k in range(len(s)):
if not visit[k] and s[k] not in sameMark:
sameMark.add(s[k])
visit[k] = True
temp.append(s[k])
f(temp)
visit[k] = False
temp.pop()
f([])
return ans
总结
根据以上题目可以发现，迷路机器人 矩阵中找包含字符串的路径，求单个结果的，visit等标记加在for前， 这类题目的模板是
def backtrack(i,j):
if not ..
更新结果
return True
visit(i,j)=true
path.append(i,j)
for k in dirs:
if backtrack(i+dirs[k], j+dirs[k+1]):
return
visit(i,j) = fase
path.pop()
而集合类或者需要每天挑一个加入path的，需要多个结果的，需要在for里进行回溯。
def f(temp):
if len(temp) == len(s):
nonlocal ans
ans.append("".join(temp))
return
sameMark = set()
for k in range(len(s)):
if not visit[k] and s[k] not in sameMark:
sameMark.add(s[k])
visit[k] = True
temp.append(s[k])
f(temp)
visit[k] = False
temp.pop()
排列组合去重：
- 子集、组合：if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
- 排列，因为是全排列，只能visit数组标记了，不swap的话，也可以进行排序，然后比较S[k]==S[k-1]。