深度优先搜索（Depth-First-Search,DFS）
类似于树的先序遍历，这种搜素算法尽可能深的去搜索一个图
参考链接：
https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
DFS和回溯算法的区别：
DFS:一种用于遍历或搜索树或图的算法，尽可能深的搜索树的分支，当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
回溯算法：采用试错的思想，尝试分步的去解决问题，在分步解决的过程中，当尝试发现有的分步答案不能得到有效的正确的解答的时候，取消上一步甚至上几步的计算，再通过其他可能的分步解答再次尝试寻找问题的答案。反复重复上诉过程后会有两种情况：
- 找到一个可能存在的正确的答案
- 再尝试了所有可能的分步办法后宣告该问题没有答案。
DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置，它强调了回退操作对于搜素的合理性，DFS强调一种遍历的思想。（广度优先遍历是另外的一种思想）
与动态规划的区别：
共同点：用于求解多阶段的决策问题
- 求解一个问题分为很多的步骤（阶段）
- 每一个步骤（阶段）可以有多种选择
不同点： - 动态规划只是要求我们评估最优解是多少，最优解对应的具体解是什么并不要求，很适合应用于评估一个方案的效果
- 回溯算法可以得到所有方案（最优解含在内），本质是一种遍历算法，时间复杂度很高
何时使用回溯算法：
当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止。一般题目中看到需要求所有可能的结果，而不是结果个数的时候，我们就需要用暴力搜索所有的可行解，可以采用回溯法。
递归函数的下面就是回溯的逻辑
树具有天然的递归：一般这种回溯的题目都是用的树来理解十分的清晰
树的宽度用一个for循环来遍历，树的深度就是用的递归的性质
对于剪枝的理解：
回溯算法的时间复杂度很高，在遍历的时候如果 能提前知道这一条分支不能搜索到满意的结果，就可以提前结束，加快搜索速度，有时候也需要做一些预处理（排序）才能达到剪枝的目的，预处理也耗时间，但是能够剪枝节约的时间更多。本质上是一种技巧，需要根据不同问题的场景采用不同的剪枝策略，需要在做题的过程中不断的进行总结。由于时间复杂度高，能够用空间换时间就尽量的换。
一般来说回溯算法的思考步骤如下：
（结合子集的题目来重点分析将大部分回溯算法的题目掌握清楚，当作一套模板背一下）
- 画出递归树，找到状态变量（当画出树形图之后，整个思路就会一目了然，回溯函数的参数）：不断的去思考
- 分支如何产生
- 题目需要的解在哪里？是在叶子节点，还是在非叶子节点，还是从根节点到叶子节点的路径？
- 哪些搜索会产生不需要的解？产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
- 寻找结束条件，由于回溯算法是借助递归实现的，所以就是需要去寻找递归的终止条件（当前想要遍历的元素操作数组的长度）
- 确定选择列表，即需要把什么数据存储到结果里面
- 判断是否需要剪枝，去判断此时存储的数据是否之前已经被储存过（子集II,组合总和II,除去一些不符合题目要求的数，一些比较垃圾的逻辑，需要提前一步剪短）
- 做出选择，递归调用该函数，进入下一层继续搜索
- 撤销选择，回到上一层的状态（5和6就是通过两个函数来执行选与不选的操作的）
回溯算法的模板
（参考东哥的算法小抄的理解）
ressult=[]
def backtrace(路径，选择列表):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
做选择
backtrace(路径，选择列表)
撤销选择
根据书上的额一些讲解，整理一些相对比较重点的点：
- 核心就是for 循环里面的递归，在递归调用前做选择，在递归调用之后做撤销选择
- 定义的回溯函数就像时一个指针，在决策树上进行遍历，同时正确维护每个节点的属性，每当走到树的底层，其”路径”就是一个子集（以子集举例）
- 前序遍历的代码：在进入某个节点之前的那个时间点执行；后序遍历的代码：在离开某个节点之后的那个时间点执行
- 做选择：从选择列表中拿出一个作为选择，并将它加入路径之中
- 撤销选择：从路径中拿出一个选择，将它恢复到“选择列表中”
在写一遍框架模板：(加深印象)
for 选择 in 选择列表:
# 做选择
将该选择从列表中移除
路径.append(选择)
backtarce(路径，选择)
# 撤销选择
路径.pop(选择)
将该选择恢复到选择列表中
这里既然已经谈到了回溯的算法（DFS）,也顺便把广度优先搜索的也整理一下，相应的思想要做一些区分的工作，而且层序遍历、滑动窗口的最大值这两道题也用到了BSF的思想还有二叉树的最小高度
主要是想把BFS的框架整理一下：
# 未完待续
# 计算从起点start到终点tareget的最短距离
def bfs(start,target):
q=queqe() # 核心数据结构
visted=[] #避免走回头路
# 将起点加入队列中
q.add(start)
visited.append(start)
step = 0 # 记录扩散的步数
while q not empty:
n=len(q)
# 将当前队列中的所有结点向四周扩散
for i in range(n):
cur=
以下为回溯法的一些题目，这里先做一些汇总如下：主要是做了这么多的题目要找到相应的一些套路是十分重要的，多做总结，多归类才能进步的更快，一点一滴的要整理清楚。
岛屿问题
- leetcoad200-岛屿数量（很经典，值得多做，而且里面的方法也是值得在很多题目里面借鉴的）
子集问题
- leetcoad78-子集（*）
- leetcoad90-子集II（**）：需要排序，然后还要剪枝
组合问题：
- leetcoad77-组合（*递归出口地条件比较特殊）
- leetcoad39-组合总和（**递归出口地条件有两个：目标值小于和目标值等于0，后续地一切元素地选择只能从函数地参数开始）
- leetcoad40-组合总数II（***在组合总和地基础上其他条件不变，附加需要对元素先排序，然后再剪枝）
- leetcoad216-组合总和III（暂时未涉及）
排列问题：
- leetcoad46-全排列
- leetcoad47-全排列II
leetcoad200-岛屿数量(****)
非常好的一道题，值得认真反复的回味清楚，而且可能还有其他的一些解法什么的，都是需要理解的，也是很基础的DFS的题目，是一道很单纯的题目，每次做一遍都会有新的发现,做个10几遍都不为过。
解题思路：
- 创建一个同样大小的二维网格mark(初始化每个都是0)：用这个网格来统计二维数组中的岛屿数量的
- 每次判断网格是1的时候就记录下来，开始按照上、左、下、右的顺序去搜索当前的网格
- 0代表当前网格没有被访问，1代表当前网格被访问了
- 遍历二维网格，对每行、每列进行一个访问
- 如果发现（i，j）是没有标记的陆地
- 对该位置进行搜索，调用DFS函数
- DFS函数的书写：
- 先找一个已经遍历的
- 定义方向组
- 通过for循环来找到相邻的四个方向
- 如果新的方向发生了越界（超出了数组边界）
- 跳出循环
- 如果发现新的位置是陆地，并且没有被标记过
- 递归搜索函数发现新的位置（用递归的时候就要注意将标记改为1，防止被重复的访问，找到一处就标记一处）
- 搜索完之后，岛屿数量+1
- 每次完成一次搜索，都会往前回退（原路返回，回退一步就扩大岛的面积，不断扩大，直至形成一个孤岛）
- 如果新的方向发生了越界（超出了数组边界）
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# count 代表岛屿数量
count=0
# mark 标记已经搜索的位置，大小与 grid 一致(这里需要理解，这里借助的是另外的数组，没有更改原数组的值，有些题解中，将原来为1的值经过搜索后改为0，直到搜索后不再发现0为止)
# mark 初始化为 0，代表当前网格没有被访问
mark=[[0]*len(grid[0]) for _ in range(len(grid))]
# 遍历 grid，对每行每列都进行访问
for i in range(len(grid)):
for j in range(len(grid[i])):
# 如果发现位置 （i ，j）是没有标记的陆地(是陆地，并且没有被搜索过)
if grid[i][j] =="1"and mark[i][j]==0:
# 对该位置进行搜索，看看有没有其他的陆地和它共同的组成岛屿
# 调用私有函数
self.DFS(grid,i,j,mark)
# 对 （i ，j）完成搜索后，岛屿数量加 1
count +=1
return count
# 将 grid 中与 x ，y 相连的位置在 mark 中进行标记
# x表示行坐标，y表示列坐标
def DFS(self,grid,x,y,mark: List[List[str]]) :
# 当前搜索位置在 mark 中标记为 1 ，代表已经遍历了
mark[x][y]=1
# 循环遍历当前位置的上、下、左、右四个方向，这里写成了循环的方式，有的地方是分别按照4个敌对来写的
for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)):
# newX 代表新的行
newX=dx + x
# newY 代表新的列
newY = dy + y
# 如果新的位置超出了数组边界
# x坐标超出左右边界，y坐标超出上下边界
if newX< 0 or newX>=len(mark) or newY <0 or newY >=len(mark[newX]):
# 跳出该位置
continue
# 如果发现新位置是陆地，并且没有被标记过
if grid[newX][newY]=="1" and mark[newX][newY]==0:
# 递归搜索新的位置，查看是否还有新的位置是陆地，共同的加入形成岛屿
self.DFS(grid,newX,newY,mark)
# 算例（和自己的手抄笔记匹配的）
# [["1","1","1","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
# 输出 ：3
# 尝试简化一些写法
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count=0
mark=[[0]*len(grid[0]) for _ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] =="1"and mark[i][j]==0:
self.DFS(grid,i,j,mark)
count +=1
return count
def DFS(self,grid,x,y,mark: List[List[str]]) :
mark[x][y]=1
for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)):
newX=dx + x
newY = dy + y
if newX< 0 or newX>=len(mark) or newY <0 or newY >=len(mark[newX])
continue
if grid[newX][newY]=="1" and mark[newX][newY]==0:
self.DFS(grid,newX,newY,mark)
5月1日再次回顾：也不知道这是自己写的第几遍的过程了，但是还是存在问题，这里将问题记录如下，不仅是算法思维要正确，同样的代码也要过关才行，否则就是一堆的bug：
- 问题一：边界出现问题。
，dfs函数里面的x和y为矩阵的行坐标和列坐标（从0开始的），出界的条件是x>=行数，y>=列数 - 问题二，
判断条件漏写，这里在最后的时候，满足搜索条件有两个，一个是当前访问的是陆地，另一个是当前这块陆地没有被标记。 - 问题三，这里不像其他的复杂的回溯问题，没有取消元素选择并弹出元素的过程。
甚至还可以采用并查集的思想来做题（主要是理解思路 ）
参考链接：https://liweiwei1419.gitee.io/leetcode-algo/2017/10/26/leetcode-algo/0200-number-of-islands/
设计算法如下：
- 如果是陆地，尝试与周围合并
- 如果是水域，把水域合并在一起
需要注意的点： - 将二维数组与一维数组进行互换的过程需要熟悉（x*列数+y）
- 对水域也需要计数
- 最后的数量=原数组数量-陆地连通后减少的数量-水域的数量（其实是有一点间接的感觉，不过也是主流的做法之一）
- 和DFS一样，也是需要做边界情况的判断
# 后续代码自己整理
# 值得自己反复的做多遍，因为是python，所以有些代码相教Java是做了一些简化的
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 边界条件
if not grid:return 0
m,n = len(grid),len(grid[0])
# 水域的数量
water = 0
# 1. 初始化并查集
# 一行代码解决,注意数组的大小
p = [i for i in range(m*n)]
# 2. 开始遍历，合并为1的节点
for i in range(m):
for j in range(n):
# 如果存在陆地，调用_union函数,将所有的陆地进行合并
# 需要把二维问题转化为一维问题
if grid[i][j]=='1':
# self._union(p,i,j)，这是适用于一维的情况
# 合并上下左右为1的节点,改为一个共同的祖先
directions = [(-1,0),(1,0),(0,-1),(0,1)]
for x,y in directions:
x= x + i
y= y + j
# 对于新的行和列，如果行列都不越界，并且此时的标记也是为1的话，就进行合并祖先的操作。
if x >=0 and y >=0 and x <m and y <n and grid[x][y]=='1':
# 经过union操作后，祖先都变为相同了，此时数组的值并没有改变，但是下一次遍历到数值虽然是1，祖先已经被同化了
self._union(p,x*n+y,i*n+j)
else:
# 把水域的数量+1
water +=1
# 3. 看n里面总共有几个parent
# 这里取值的问题
# return len(set([self._parent(p,i) for i in range(m*n)]))
res = [self._parent(p,i) for i in range(m*n)]
return len(set(res))-water
# _union和_parent直接按模板抄上来
def _union(self,p,i,j):
p1 = self._parent(p,i)
p2 = self._parent(p,j)
p[p2]=p1
# 类似于find函数
def _parent(self,p,i):
root = i
# 本质上也是一个递归操作
while p[root] != root:
root = p[root]
# 路径压缩
while p[i] != i:
x ,i,p[x] = i,p[i],root
return root
对python代码做一点修改，主要是为了和java以及主流的代码思路保持一致
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 边界条件:如果网格为空或者行数为0,直接返回空
if grid is None or len(grid)==0: return 0
# 统计水域的数量,初始化为0
waters = 0
# 为了方便调用函数,因为union find和getCount都在uf类之下
uf = UnionFind(grid)
m,n=len(grid),len(grid[0])
for i in range(m):
for j in range(n):
# 如果发现的是水域,就把水域数量+1
if grid[i][j]=='0':
waters +=1
# 如果是陆地,就需要朝四个方向进行搜索
else:
# 合并上下左右为1的节点,改为一个共同的祖先
# 合并上边节点(i-1,j)，注意不能出界
directions = [(-1,0),(1,0),(0,-1),(0,1)]
for x,y in directions:
x= x + i
y= y + j
# 对于新的行和列，如果行列都不越界，并且此时的标记也是为1的话，就进行合并祖先的操作。
if x >=0 and y >=0 and x <m and y <n and grid[x][y]=='1':
uf.union(x*n+y,i*n+j)
return uf.getCount() - waters
# 定义UnionFind类,当作模板
class UnionFind:
# 方法,类似于构造一个和网格类似的一维数组
def __init__(self,grid):
m,n=len(grid),len(grid[0])
# 创建一个一维的root数组,长度与grid的长度相同
self.root= [-1]*m*n
# 一开始初始化为多少个元素
# 最终应该减去水域的个数-联通之后的减少的个数
self.count = m*n
for i in range(m*n):
self.root[i]=i
def find(self,x):
if x ==self.root[x]:
return self.root[x]
else:
self.root[x]=self.find(self.root[x])
return self.root[x]
def union(self,x,y):
rootX = self.find(x)
rootY = self.find(y)
if rootX !=rootY:
self.root[rootX] = rootY
self.count -=1
def getCount(self):
return self.count
在上面的一个题解的基础上做进一步的优化（建议把上面的几种方式十分熟练之后再做相应的处理，还会让自己更上一步台阶）
优化的两个点：参考资料https://www.bilibili.com/video/BV1Q5411H7v5?p=2
- 优化包括quick find和quick union,这里主要还是quick union,对树的高度进行了优化，权重的优化
- 对搜索的方向进行了优化（这个只是作为平时的解答，在面试的时候，还是按照常规思路来作答比较的好）
# 定义UnionFind类,模板,但是也是做了一定的修改的.(根据题目的不同)
class UnionFind:
# 方法,类似于构造一个和网格类似的一维数组
def __init__(self,grid):
m,n=len(grid),len(grid[0])
# 创建一个一维的root数组,长度与grid的长度相同
self.root= [-1]*m*n
# 定义了一个rank数组，记录每一组树的高度，初始化为0
self.rank = [0]*m*n
# 一开始初始化为0
self.count = 0
for i in range(m):
for j in range(n):
# 以下的代码既构造一个序列号==祖先的数组,同时还记录了陆地的数量
if grid[i][j]=='1':
self.root[i*n+j]=i*n+j
self.count+=1
def find(self,x):
if x ==self.root[x]:
return self.root[x]
else:
self.root[x]=self.find(self.root[x])
return self.root[x]
def union(self,x,y):
rootX = self.find(x)
rootY = self.find(y)
if rootX !=rootY:
# 再加入一个判断,保证并查集不会退化为单链,树形结构尽量的矮一点,从而快速获得结点的根
# 比较两个树的树高,rootX的树高小于rootY的树高，把矮的树连接到高的树上面去
# 即把rootX的根节点放到rootY
if self.rank[rootX] <self.rank[rootY]:
rootX,rootY=rootY,rootX
# 否则：把rootY的根节点放到rootX(把 y连到x)
self.root[rootY] = rootX
# 以上的三行代码是做了相应的优化的实际上是这四行代码
# if self.rank[rootX] <self.rank[rootY]:
# self.root[rootX] = rootY
# elif self.rank[rootX] <self.rank[rootY]:
# self.root[rootY] = rootX
elif self.rank[rootX] ==self.rank[rootY]:
self.rank[rootX] +=1
self.count -=1
def getCount(self):
return self.count
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 边界条件:如果网格为空或者行数为0,直接返回空
if grid is None or len(grid)==0: return 0
# 为了方便调用函数,因为union find和getCount都在uf类之下
uf = UnionFind(grid)
m,n=len(grid),len(grid[0])
for i in range(m):
for j in range(n):
# 如果是陆地,就需要朝四个方向进行搜索
if grid[i][j]=='1':
# 合并上下左右为1的节点,改为一个共同的祖先
# 合并上边节点(i-1,j)，注意不能出界
# directions = [(-1,0),(1,0),(0,-1),(0,1)]
# 对于方向向量,可以只用右边和下边
directions = [(1,0),(0,1)]
for x,y in directions:
x= x + i
y= y + j
# 对于新的行和列，如果行列都不越界，并且此时的标记也是为1的话，就进行合并祖先的操作。
if x >=0 and y >=0 and x <m and y <n and grid[x][y]=='1':
uf.union(x*n+y,i*n+j)
# if i+1<m and grid[i+1][j]=='1':
# uf.union((i+1)*n+j,i*n+j)
# if j+1<n and grid[i][j+1]=='1':
# uf.union(i*n+j+1,i*n+j)
return uf.getCount()
N皇后问题
解题思路：
用空间换时间的操作
一旦发现是错的，就需要推到重来
还有浅拷贝和深拷贝的情况：值传递和引用传递的区别
运用数学公式去更新棋盘
回溯和递归的关系：用递归的代码来解决回溯的算法，需要把某些代码做一个重置、剪枝操作（一定要深入理解递归的算法）
- 构建两个数组,一个数组是攻击数组:attack(是否可以放置皇后)
# 待整理
leetcoad78-子集(middle)
非常重要-重点掌握，每一行代码都要清楚，并且还要清楚相应的调试过程，把DFS+剪枝的操作掌握得烂熟于心的程度（本题没有剪枝过程），由子集的解题步骤衍生出的7道题目的写法
方法一：采用树形递归的方式（结合树形图理解相应的递归路线，本质是一种深度优先搜索DFS）
结合着张图以及后面自己在本地调式的过程，基本上是把这个过程给完完全全的整理清楚了。
方法二：采用循环的思路来解决（与方法一的区别：把子集加入结果数组的时机不一样，本质的思路是一样的）
方法三：采用广度优先搜索（BFS）,是一种分层搜索的方法，不是递归形式的，不需要回退
函数：
- 每次调用这个函数，我们都会在当前数组中可用的区间中搜索出一个元素来，每找到一个元素就在原先的路径上添加的一个元素，此时你无论添加一个什么样的元素，当前都已经有一条完整的路径了，形成的一个路径就是一个子集，加入到我们的结果数组中
- i肯定会超过数组，一旦超过数组的话，就结束相应的判断，否则的话：确定选了1之后，开始查看后面有多少种选择，利用三行代码把所有的子集添加进去：
- 利用subset.add扩充新的元素进去，判断是否需要剪枝，去判断此时储存的数据是否之前已经被储存过
- 做出选择，递归调用该函数，进入下一层继续 （当前的这个搜索区间不再是从2开始的，从2的后面的元素开始的。）backtrack
- 撤销选择，回到上一层的状态：subset.remove
看视频做的一点记录：
对于每个元素都有两种选择方案：选或者不选，总共有2^n种
无法利用一次循环来把所有的元素都选出来：对于某个元素做出选或者不选的决定后，之前选择的元素与该元素共同组成一个新的组合，会漏掉一个不选的元素
把选1的策略全部走完
然后把选2的策略全部走完
# 按照吴师兄的思路一步步的调试清楚
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# 结果集合
sets=[]
#每次的子集
subset=[]
# 执行回溯算法
self.backtrack(0,nums,subset,sets)
# 返回结果
return sets
# i 表示递归时正在访问的数组元素下标
# nums 表示当前集合中的元素
# subset 表示每次递归后生成的子集，就是路径上的那些元素,类似于临时的子数组
# sets 表示最终生成的所有子集合
# 画出递归树，找到状态变量（回溯函数的参数）
def backtrack(self,i:int,nums:List[int],subset:List[int],sets:List[List[int]]) -> List[List[int]]:
# 每次确定好一个子集，都把它加入到结果集合中
sets.append(subset[:])
# 此处在调试的时候加入一个打印，有助于了解相应的不断递归过程
# print(" 递归前subset => " ,subset)
# print(" 递归前sets => " ,sets)
# 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
# 本题中可以不加这个判断，大家可以思考一下为什么可以不加，结合 for 循环的边界来思考
n = len(nums)
# 当访问的数组下标超过了nums数组的长度时，递归结束（这里的理解非常重要，只有递归结束了，才会有回溯的操作过程，这是一体的）
# 此处也可以不加判断，理由，通过调试的过程中我们就会发现，当n=len(nums)的时候，此时不会进入到循环之中，直接跳到subset.pop(len(subset) - 1)这一行代码，类似于是递归的最后一次循环了。
if i >=n:
return
# 3、确定选择列表，需要把什么数据存储到结果里面
# for 循环就是一个选择的过程
# 遍历本层集合中的元素
for j in range(i,n):
# 把本次递归访问的元素加入到 subset 数组中
subset.append(nums[j])
# 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
# 本题不需要剪枝
# 5、做出选择，递归调用该函数，进入下一层继续搜索
# 递归
# 此时需要传入新的参数
self.backtrack( j+1,nums , subset , sets)
# 6、撤销选择，回到上一层的状态
# 取消对 nums[i] 的选择（这里的取消选择的过程，自己也可以通过代码来进行调试，让自己更加熟悉这个过程：只有在递归到尽头的时候才会进行回溯的操作）
subset.pop(len(subset) - 1)
#print(" 取消subset最后一个元素 => " ,subset)
# 头文件
if __name__ == '__main__':
# 输入一个特定的需要求解的数组
nums = [1,2,3]
res = Solution().subsets(nums)
#print(res)
print(" 输出 => " ,res)
# 输出结果如下
# 一开始就选1时，从头递归到尾
# 递归前subset => []
# 递归前sets => [[]]
# 递归前subset => [1]
# 递归前sets => [[], [1]]
# 递归前subset => [1, 2]
# 递归前sets => [[], [1], [1, 2]]
# 递归前subset => [1, 2, 3]
# 递归前sets => [[], [1], [1, 2], [1, 2, 3]]
# 一开始就选1时，从递归结束的地方开始回溯
# 取消subset最后一个元素 => [1, 2]
# 取消subset最后一个元素 => [1]
# # 一开始就选1时，回退到选3不选2的过程
# 递归前subset => [1, 3]
# 递归前sets => [[], [1], [1, 2], [1, 2, 3], [1, 3]]
# 取消subset最后一个元素 => [1]
# 取消subset最后一个元素 => []
# 回退到空，然后开始选2的过程
# 递归前subset => [2]
# 递归前sets => [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
# 递归前subset => [2, 3]
# 递归前sets => [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
# 选2的时候递归结束开始回溯的一个过程
# 取消subset最后一个元素 => [2]
# 取消subset最后一个元素 => []
# 回退到空，然后开始选3的过程
# 递归前subset => [3]
# 递归前sets => [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
# 回退到空，然后开始选3的下一个元素的过程（发现此时已经无元素可以选择了）
# 取消subset最后一个元素 => []
# 最终对sets进行输出
# 输出 => [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
# 自己对代码做一点简化，比如我把函数写在了subsets里面，就不需要再另外的去定义sets和subset变量。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
sets=[]
subset=[]
def backtrack(i:int,nums):
sets.append(subset[:])
# print(" subset => " ,subset)
# print(" sets => " ,sets)
n = len(nums)
if i >=n:
return
for j in range(i,n):
subset.append(nums[j])
backtrack( j+1,nums )
# 弹出subset中的最后一个元素
subset.pop()
# print(" 取消subset最后一个元素的选择 => " ,subset)
# 调用回溯算法
backtrack(0,nums)
# 返回结果
return sets
迭代法（待整理）
参考链接：https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in nums:
res = res + [[i] + num for num in res]
return res
leetcoad90-子集II(middle)
相比于子集，加入了一个剪枝的操作：判断当前的元素是否和之前的元素相同，如果相同就不去执行后面的代码。（后面的代码是将当前元素作为一种选择情况下的那一个子集加入到相应的结果数组中，当前的情况已经在之前分析过了，不需要再执行了,子集那道题已经限制了给定的值是互不相同的）
# 并加入头文件进行调试，选用的例子是nums=[1,2,2],如果选用[1,2,3],得到的结果和子集I是一样的结果
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
# 对原数组排序，这样才能对比当前元素和之前的元素是否相同
nums.sort()
sets=[]
subset=[]
def backtrack(i:int,nums):
sets.append(subset[:])
n = len(nums)
if i >=n:
return
for j in range(i,n):
# 剪枝
if j >i and nums[j-1]==nums[j]:
continue
subset.append(nums[j])
backtrack( j+1,nums )
# 弹出subset中的最后一个元素
subset.pop()
# 调用回溯算法
backtrack(0,nums)
# 返回结果
return sets
# 头文件
if __name__ == '__main__':
# 输入一个特定的需要求解的数组
nums = [1,2,2]
res = Solution().subsetsWithDup(nums)
#print(res)
print(" 输出 => " ,res)
# 输出结果如下：
# 一开始就选1时，从头递归到尾
# subset => []
# sets => [[]]
# subset => [1]
# sets => [[], [1]]
# subset => [1, 2]
# sets => [[], [1], [1, 2]]
# subset => [1, 2, 2]
# sets => [[], [1], [1, 2], [1, 2, 2]]
# 一开始就选1时，从递归结束的地方开始回溯，由于后面还有一个2，与上一次选择相同，不会再选择，直接回溯到空
# 取消subset最后一个元素的选择 => [1, 2]
# 取消subset最后一个元素的选择 => [1]
# 取消subset最后一个元素的选择 => []
# 回退到空，然后开始选2的过程
# subset => [2]
# sets => [[], [1], [1, 2], [1, 2, 2], [2]]
# subset => [2, 2]
# sets => [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
# 取消subset最后一个元素的选择 => [2]
# 取消subset最后一个元素的选择 => []
# 回退到空，然后开始选2的下一个元素的过程（发现此时已经无元素可以选择了）
# 输出 => [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
leetcoad77-组合(middle)
题目描述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
做题链接：https://leetcode-cn.com/problems/combinations/
做题思路：
这里用4个元素中找出3个数的组合来解题
- 理解题目的意思：当前总共有三个坑，如何从四个元素中去寻找三个元素去填满这些坑，可以将数组中的每一个元素作为三个坑的第一个元素，然后在剩下的三个元素中去寻找两个元素出来，将剩下的这两个坑填满。然后在填了两个坑的基础上，查看后面的以后个坑如何选择
- 实现地具体过程以及相应地注意点：
- 递归地终止条件变了：需要填入地数为0
- 确定选择列表地时候也变了，选择地终止索引为后面地数刚好能凑齐k个数截至（想要保证数不重复，又要把元素填满）
暂时没有代码，待补充
leetcoad39-组合总和(middle)
题目描述：
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
理解题目的意思之后再谈做题的方法：
- 仍然可以用回溯的算法思想
- 第一次是可以选择任意元素，在第一次选择的基础上，剩下的就是要凑出target-nums[i]的和，然后继续进行下一轮的选择，在选数的时候不能选比当前需要值大的数。
以下结合这几张图来辅助理解这里的过程
- 罗列所有选择并排除不合适的选择，这样就选出了[2,2,3] [2,3,2] [3,2,2] [7],但是这和题目的意思是不符合的，组合的话是不用管顺序的
- 紧接着就思考，如何进行剪枝的问题？对于想要凑齐5的情况，由于第一次已经选了2 2 3，当下一次选到2 3的时候就会发现之前是舍弃了2没有选的，那么在接下的选择中就也不能选择2，只能从3开始选择，同理在凑齐4的过程中，由于前面是选择了3的，所以后面就不能再选比3小的数，也就只能从3开始选，也就有了下面的这张图的理解过程
- 再紧接着就思考递归结束的条件：
1. target<0
2. target==0
4.再接着就是确定选择列表，需要将什么样的数加入进去，精髓就在于递归的时候传入的数据：backtrack(nums,target-nums[i],path,newposition)
5.初调用函数的时候表示：从第0个元素开始选择，要筹齐的目标数为原始目标数，然后随着不断地递归,target不断地减小，最后达到递归地出口地位置。
# 采用吴师兄的思路
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path =[]
res = []
self.backtrack(candidates,target,path,0,res)
return res
# 画出递归树，找到状态变量
# strat表示递归正在访问的数组元素下标
# target表示想在当前区间拼凑出的目标值
# path表示路径
def backtrack(self,nums,target,path,start,res):
n = len(nums)
# 2.寻找结束条件（也即寻找递归的终止条件,这里有两个）
if target <0:
return
# 找到一个组合
if target==0:
res.append(path[:])
return
# 3.确定选择列表，需要把什么数据传入里面
# for 循环就是一个选择的过程
# i 等于 start 表示，后续可以选的元素一开始只能从 start 开始
# 比如 nums = [2,3,6,7]
# i = 1，指向了元素 3 ，表示当前后续选择的过程中，只能从 3 开始选，可以重复选 3 ，但无法选 2 了
# i = 2，指向了元素 6 ，表示当前后续选择的过程中，只能从 6 开始选，可以重复选 6 ，但无法选 2、3 了
for i in range(start,n):
# 当前路径上可以把 nums[i] 加上
path.append(nums[i])
# 一些逻辑操作（可有可无，视情况而定）
# 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
# 需要剪枝
# 此时，目标值 target，已经从 target 变成了 target - nums[i]
# 接下来需要去【某个区间中】拼凑 target - nums[i]
# 由于 同一个 数字可以 无限制重复被选取
# 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，依旧可以继续从使用 nums[i] 开始
# 而 i 前面的元素，比如 num[i-1]、 num[i-2]无法继续使用，实现了剪枝操作
nowposition = i
# 5、做出选择，递归调用该函数，进入下一层继续搜索
# 递归
self.backtrack(nums, target - nums[i] , path , nowposition,res )
# 一些逻辑操作（可有可无，视情况而定）
# 6、撤销选择，回到上一层的状态
path.pop()
# 自己在此基础上做了一点简化代码的工作
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path =[]
res = []
# 定义回溯函数
def backtrack(nums,target,path,start):
n = len(nums)
# 寻找结束条件
if target <0:
return
if target==0:
res.append(path[:])
return
# 3.确定选择列表，需要把什么数据传入里面
# for 循环就是一个选择的过程
for i in range(start,n):
path.append(nums[i])
#4、判断是否需要剪枝
nowposition = i
# 5、做出选择，递归调用该函数，进入下一层继续搜索
# 递归
backtrack(nums, target - nums[i] , path , nowposition )
# 6、撤销选择，回到上一层的状态
path.pop()
# 调用回溯函数
backtrack(candidates,target,path,0)
return res
leetcoad40-组合总数II(middle)
题目描述：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。(和上面一题的区别：在candidate中找的数字只能使用一次，但是给定的数组可能含有相同的值)
注意：解集不能包含重复的组合。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 对数组进行一个排序操作
candidates.sort()
path =[]
res = []
# 定义回溯函数
def backtrack(nums,target,path,start):
n = len(nums)
# 寻找结束条件
if target <0:
return
if target==0:
res.append(path[:])
return
# 3.确定选择列表，需要把什么数据传入里面
# for 循环就是一个选择的过程
for i in range(start,n):
#4、判断是否需要剪枝
# 之所以限定i > strat,是为了保证i-1是有值的
if i >start and nums[i-1] ==nums[i]:
continue
path.append(nums[i])
nowposition = i+1
# 5、做出选择，递归调用该函数，进入下一层继续搜索
# 递归
backtrack(nums, target - nums[i] , path , nowposition )
# 6、撤销选择，回到上一层的状态
path.pop()
# 调用回溯函数
backtrack(candidates,target,path,0)
return res
组合总和III
题目描述：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
解题思路：和lc77.组合相比，本题多了一个步骤：判断已经拿到的k个数之和是否等于n。
化简题意：从[1,9]中找k个数，使得它们的和是否等于n。
如何做？模拟人工寻找过程，先选1、2、3发现它们的和不等于n，下一步我们会保留1、2，舍弃3，添加4进来再次判断，以此类推，[1、2、5]、[1、2、6]…当最后一位数字3~9全都试过之后，我们再去改变第二位数….
待整理
leetcoad46-全排列(middle)
注意与子集的区别的地方：
- 对前面已经用过的数字，后面还是可以再继续用（对于123和23在排列里面是不同的组合，在子集中就是相同的组合）
- 只有当搜索到的数组的长度等于原数组的长度才会进行返回（全排列需要把所有的数都要加进来的）
需要建立一个布尔类型数组：用来判断每个元素在后面的遍历过程中没有使用
一开始默认的每一个元素都没有被选中
创建回溯函数：
几个参数：数组、路径、几个当前的元素在之前的遍历过程中有没有被使用过的数组
只有当前元素还没有被用到过，才有资格加入到我们的数组中
把当前的这个元素设置为true的操作，表明已经选择的数字在当前要选择的数字中不能出现
由于要遍历所有的元素，相当于是一个暴力的解法，不存在剪枝操作
递归的调用代码，进入下一层的搜索
取消对nums[i]的选择（这里的理解很重要：在每次的遍历过程中，先是设置为了true,方便进行递归，但是在一轮循环中，这个被置为true的数仍然要被用到，需要加入取消对nums[i]的选择） - 先写以 111 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；
- 再写以 222 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
- 最后写以 333 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 结果集合
sets=[]
#每次的子集
subset=[]
# 创建一个布尔数组
# 每个元素默认一开始没有被选择，后面当我们选定一个数的时候，将这个数组的相应位置设置为true，在考虑下一个位置的时候能够以O(1)的时间复杂度判断是否被选择过，是一种以空间换时间的思想
n = len(nums)
used = [False]*n
# 执行回溯算法
self.backtrack(nums,subset,used,sets)
# 返回结果
return sets
# used表示递归时正在访问的数组元素是否之前已经被访问过
# nums 表示当前集合中的元素
# subset 表示每次递归后生成的子集，就是路径上的那些元素,类似于临时的子数组，就是充当了一个栈的作用
# sets 表示最终生成的所有子集合
# 画出递归树，找到状态变量（回溯函数的参数）
def backtrack(self,nums:List[int],subset:List[int],used:List[int],sets:List[List[int]]) -> List[List[int]]:
# 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
# 当访问的数组长度等于原数组的长度，递归结束
# 每次确定好一个子集，都把它加入到结果集合中
n = len(nums)
if len(subset)==n:
sets.append(subset[:])
return
# 3、确定选择列表，需要把什么数据存储到结果里面
# for 循环就是一个选择的过程
# 遍历本层集合中的元素
for i in range(0,n):
# 当前是哪些元素可以加入
# 如果当前的元素的布尔值是False,那么就可以选择该元素
if used[i]==False:
# 把本次递归访问的元素加入到 subset 数组中
# 往下走一层，subset在尾部追加
subset.append(nums[i])
# 这个元素已经被使用过，就用更改标记
# 在一轮还没有选完的过程中，标记了这个就表明如果循环到这里了需要跳过，这个元素已经选过了，需要选择下一个。
used[i]=True
# 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
# 本题不需要剪枝
# 5、做出选择，递归调用该函数，进入下一层继续搜索
# 递归的调用代码（暴力的过程）
self.backtrack( nums,subset ,used,sets)
# 6、撤销选择，回到上一层的状态（上面的一轮搜索到底执行完毕就回撤，这里的理解要结合调试的过程来理解，其实如果是例子很简单还比较好理解，一旦例子过于复杂就会出现问题，所以主要还是在于思想的方面）
# 取消对 nums[i] 的选择(从最后一个加入的元素开始的)，这两行代码是配套操作的，两个都不能少（也需要结合调试的过程来理解）
# 回溯的过程，不断地往前，将之前变为True的标记一个一个的变成False，索引号一是从大变小的
used[i]=False
# 把当前元素移除我们的路径，在这一次循环里面，比如1设置为true，它不会在进入if语句。
# 往上走一层，subset撤销上一次选择
subset.pop()
# 简化版
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
sets=[]
subset=[]
n = len(nums)
used = [False]*n
def backtrack(subset,used,sets) :
if len(subset)==n:
sets.append(subset[:])
return
for i in range(0,n):
if used[i]==False:
subset.append(nums[i])
used[i]=True
backtrack( subset,used,sets)
used[i]=False
subset.pop()
backtrack(subset,used,sets)
return sets
5月1日再次回顾的时候再看看这道题，发现还是存在一些问题没有完全的弄懂。几个重要的点再次进行回顾与整理：
- 首先在大体的思路上就出现了问题：要定义一个布尔数组，为了好进行相应的标定工作。
第一点不用说，深拷贝的问题- 对于一轮选择中的单个元素加入subset的时机的问题：只有符合筛选条件之后才能加入，不能够放错位置
- 常规步骤，在一次递归之后取消选择以及移除路径
假设每一次尝试都复制，则不需要回溯
在每一个非叶子节点分支的尝试，都创建新的变量来表示状态 - 在回到上一层节点的时候不需要回溯
- 在递归终止的时候也不要做拷贝
结果：可以得到解，但是会创建中间变量，会有空间和时间的消耗
顺便贴一个可以在本地调试的版本，还可以输出递归前以及递归后的子集的情况（在本地调试之后发现很多问题就能迎刃而解）：
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
sets=[]
subset=[]
n = len(nums)
used = [False]*n
def backtrack(subset,used,sets) :
if len(subset)==n:
sets.append(subset[:])
return
for i in range(0,n):
if used[i]==False:
subset.append(nums[i])
used[i]=True
# print(" 递归之前 => ",subset)
backtrack( subset,used,sets)
used[i]=False
subset.pop()
# print(" 递归之后 => " ,subset)
backtrack(subset,used,sets)
return sets
# 头文件
if __name__ == '__main__':
# 输入一个特定的需要求解的数组
nums = [1, 2, 3]
solution = Solution()
res = solution.permute(nums)
print(res)
# print(" 输出 => " ,res)
# 输出结果如下
# 递归之前 => [1]
# 递归之前 => [1, 2]
# 递归之前 => [1, 2, 3]
# 递归之后 => [1, 2]
# 递归之后 => [1]
# 递归之前 => [1, 3]
# 递归之前 => [1, 3, 2]
# 递归之后 => [1, 3]
# 递归之后 => [1]
# 递归之后 => []
# 递归之前 => [2]
# 递归之前 => [2, 1]
# 递归之前 => [2, 1, 3]
# 递归之后 => [2, 1]
# 递归之后 => [2]
# 递归之前 => [2, 3]
# 递归之前 => [2, 3, 1]
# 递归之后 => [2, 3]
# 递归之后 => [2]
# 递归之后 => []
# 递归之前 => [3]
# 递归之前 => [3, 1]
# 递归之前 => [3, 1, 2]
# 递归之后 => [3, 1]
# 递归之后 => [3]
# 递归之前 => [3, 2]
# 递归之前 => [3, 2, 1]
# 递归之后 => [3, 2]
# 递归之后 => [3]
# 递归之后 => []
# 输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
leetcoad47-全排列II(middle)
与全排列的区别：给定的数组可以包含重复的数字,如果给定的数组中元素互不相同，那就是一个完全的全排列的问题，所以现在考虑的就是把含有相同的元素的情况给去除掉
解决方法：
- 先对数组进行排序
- 然后对后续出现的相同的搜索进行剪枝操作
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 对原数组进行排序
nums.sort()
# 结果集合
sets=[]
#每次的子集
subset=[]
# 创建一个布尔数组
# 每个元素默认一开始没有被选择
n = len(nums)
used = [False]*n
# 执行回溯算法
self.backtrack(nums,subset,used,sets)
# 返回结果
return sets
# used表示递归时正在访问的数组元素是否之前已经被访问过
# nums 表示当前集合中的元素
# subset 表示每次递归后生成的子集，就是路径上的那些元素,类似于临时的子数组
# sets 表示最终生成的所有子集合
# 画出递归树，找到状态变量（回溯函数的参数）
def backtrack(self,nums:List[int],subset:List[int],used:List[int],sets:List[List[int]]) -> List[List[int]]:
# 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
# 当访问的数组长度等于原数组的长度，递归结束
# 每次确定好一个子集，都把它加入到结果集合中
n = len(nums)
if len(subset)==n:
sets.append(subset[:])
return
# 3、确定选择列表，需要把什么数据存储到结果里面
# for 循环就是一个选择的过程
# 遍历本层集合中的元素
for i in range(0,n):
# 如果当前的元素的布尔值是False,那么就可以选择该元素
if used[i]==False:
# 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
if i>0 and nums[i-1]==nums[i] and used[i-1]==False:
continue
# 把本次递归访问的元素加入到 subset 数组中（剪枝后再加入）
subset.append(nums[i])
used[i]=True
# 5、做出选择，递归调用该函数，进入下一层继续搜索
# 递归
# 此时需要传入新的参数
self.backtrack( nums,subset ,used,sets)
# 6、撤销选择，回到上一层的状态
# 取消对 nums[i] 的选择
used[i]=False
subset.pop()
#简化版本
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
sets=[]
subset=[]
n = len(nums)
used = [False]*n
def backtrack(subset:List[int],used:List[int],sets:List[List[int]]) :
n = len(nums)
if len(subset)==n:
sets.append(subset[:])
return
for i in range(0,n):
if used[i]==False:
if i>0 and nums[i-1]==nums[i] and used[i-1]==False:
continue
subset.append(nums[i])
used[i]=True
backtrack( subset ,used,sets)
used[i]=False
subset.pop()
backtrack(subset,used,sets)
return sets
5月1号来做，发现还是存在问题，这种小的细节根本就没法把握：
- 结果要以字典序的升序进行排列，所以要预先做一个排序工作
- 判断剪枝的操作，自己还是打盹了，说明还在犹豫，想这里面的过程
它难就难在这一步的过程