回溯算法
简介：
- 使用场景：当问题要求找出所有解集或者要求回答满足约束的最优解时，往往需要回溯法。
- 方法定义：具有限界函数的深度优先生成法称为回溯法。
- 基本做法：回溯法本质是搜索，是能避免不必要搜索的穷举式搜索。通常，回溯法在问题的解空间树中，按照深度优先策略，从根节点出发搜索解空间树。算法搜索到解空间树的任意结点时，先判断该节点是否包含问题的解：1）如果不包含，则跳过以该结点为根的树的搜索，逐层向祖先节点回溯；2）否则进入该子树，继续按深度优先搜索策略搜索；
注：这边需要注意的点是如何跳过，如何回溯？
回溯法解题框架
递归回溯
回溯法对解空间作深度优先搜索时，使用递归方法实现回溯法。
void backtrack (int t)
{
if (t>n)
output(x);
else //当前扩展节点的子树的起始/终止节点。
for (int i=f(n,t);i<=g(n,t);i++) {
x[t]=h(i);
if (constraint(t)&&bound(t))
backtrack(t+1);
}
}
迭代回溯
采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。
void iterativeBacktrack (){
int t=1;
while (t>0) {
if (f(n,t)<=g(n,t))
for (int i=f(n,t);i<=g(n,t);i++) {
x[t]=h(i);
if (constraint(t)&&bound(t)) {
if (solution(t)) output(x);
else t++;}
}
else t--;
}
}
子集树
典型例子：装载问题；0-1背包问题；最大团问题;求所有子集
void backtrack (int t){
if (t>n)
output(x);
else
for (int i=0; i<=1; i++) {
x[t]=i;
if (legal(t)) backtrack(t+1);
}
}
(leetcode-77) 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(nums,index,path,k):
if len(path) == k:
res.append(path[:])
return
for i in range(index,len(nums)):
backtrack(nums,i+1,path+[nums[i]],k)
res = []
backtrack(list(range(1,n+1)),0,[],k)
return res
(leetcode-78) 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(nums,index,path):
res.append(path[:])
for i in range(index,len(nums)):
dfs(nums,i+1,path+[nums[i]])
res = []
nums.sort()
dfs(nums,0,[])
return res
(leetcode-90) 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(nums,index,path):
res.append(path[:])
for i in range(index,len(nums)):
if i>index and nums[i] == nums[i-1]:
continue
dfs(nums,i+1,path+[nums[i]])
res = []
nums.sort()
dfs(nums,0,[])
return res
(leetcode-216) 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。说明：所有数字都是正整数。解集不能包含重复的组合
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(nums,index,n,k,path):
if 0==k and n==0:
res.append(path[:])
return
for i in range(index,9):
if nums[i] <= n:
backtrack(nums,i+1,n-sum([nums[i]]),k-1,path+[nums[i]])
res = []
nums = list(range(1,10))[::-1]
backtrack(nums,0,n,k,[])
return res
(leetcode-416) 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意:每个数组中的元素不会超过 100.数组的大小不会超过 200
注：刚开始提前判断的时候要注意各种情况，第二，学会这种只要满足就返回的方式
class Solution:
def canPartition(self, nums: List[int]) -> bool:
div,mod = divmod(sum(nums),2)
if mod==1 or max(nums)>div:
return False
tar = sum(nums)//2
def backtrack(nums,index,t,flags):
if t == 0:
return True
for i in range(index,len(nums)):
if nums[i] <= t:
if backtrack(nums,i+1,t-nums[i],flags):
return True
return False
res = []
nums.sort(reverse=True)
flags=[0]*len(nums)
if backtrack(nums,0,tar,flags):
return True
return False
(leetcode-698) 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
注：需要开动一下脑子，做一些变换。每个数一定能被分到一个集合中去
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
div, mod = divmod(sum(nums),k)
if mod!=0 or max(nums)>div:
return False
def backtrack(nums,targets,i):
if i==len(nums):
return True
for j,v in enumerate(targets):
if nums[i]<=v:
targets[j]-=nums[i]
if backtrack(nums,targets,i+1):
return True
targets[j]+=nums[i]
return False
targets = [div]*k
nums.sort(reverse=True)
return backtrack(nums,targets,0)
排列树
典型例子：全排列问题
void backtrack (int t){
if (t>n)
output(x);
else
for (int i=t; i<=n; i++) {
swap(x[t], x[i]);
if (legal(t)) backtrack(t+1);
swap(x[t], x[i]);
}
}
def perm(data,begin,end):
if begin == end:
print(data)
else:
j = begin
for i in range(begin,end):
data[i] ,data[j] = data[j], data[i]
perm(data,begin+1,end)
data[i] ,data[j] = data[j], data[i]
perm(list(range(3)),0,3)
(leetcode-46) 给定一个没有重复数字的序列，返回其所有可能的全排列。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(nums,index):
if index ==len(nums):
res.append(nums[:])
for i in range(index,len(nums)):
nums[i],nums[index] = nums[index], nums[i]
dfs(nums,index+1)
nums[i],nums[index] = nums[index], nums[i]
res = []
dfs(nums,0)
return res
(leetcode-526) 假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：第 i 位的数字能被 i 整除,i 能被第 i 位上的数字整除，现在给定一个整数 N，请问可以构造多少个优美的排列？
class Solution:
def countArrangement(self, N: int) -> int:
flags = [0]*(N+1)
nums = list(range(N+1))
self.res = 0
self.backtrack(nums,1,flags)
return self.res
def backtrack(self,nums,index,flags):
if index==len(nums):
self.res += 1
return
for i in range(1,len(nums)):
if flags[i] == 0 and (index%i==0 or i%index==0):
flags[i] = 1
self.backtrack(nums,index+1,flags)
flags[i] = 0
回溯算法三要素：
- 选择 ( choice )
- 约束 ( constraint )
- 目标 ( goal )