1. 在处理回溯问题的时候，集合的大小就是多叉树的宽度，因此采用for循环. 注意，这里根节点也会被最终pop,因为如果满足条件就会直接返回，加上后面的pop，导致根节点也会被pop。根本原因是调用回溯的时候，子函数也会进行pop操作，然后再返回，相当于什么也没加。

1. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

1. 整理比较简单，主要是for循环外面记得加return，final要append result.copy,毕竟result是临时列表
2. 组合：【1，2】和【2，1】是一样的，因此不能有重复元素。排序：【1，2】和【2，1】是不同的

2. 组合总和III

简单

3. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1. 相当于我们现在分阶段处理一个数组，只需要用start_index控制每一阶段，用字典来建立每一阶段for循环的列表即可。

4. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

1. 主要是没意识到，这个for循环数组的start_index是i而不是i+1

5.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

1. 数组中有重复元素，要保证结果中没有重复的结果，比如[1,2,5], [1,2,5]。
2. 例如[1,1,2],以第一个1开始往下取，那必定包含以第二个1开始往下取的所有结果，就会重复。因此，关键在于，同一层的树，如果相同，就要去重。
3. 关键在于树层重复的元素怎么找： 树层重复的元素，不是在循环的开头，而且数值和上一个元素相同。
   if i>start_index and nums[i]== nums[i-1]:
   continue

6. 分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

1. 一开始不会做，主要是不理解切割的环节。使用start_index作为切割线，当start_index进行到字符串的末尾时，就是结束条件。

2. result收集多个切割线，然后判断每个切割的是否符合回文。或者，可以在单层判断逻辑里，每个字串就是【start_index, i], 如果符合回文，就把字串放到result, 再对i+1进行递归。也就是说，result不再直接append,而是根据条件判断是否要append字串。

3. result里面其实存的还是i的索引，只不过是有选择地存储

class Solution:def findValue(self, start_index, s, result, final):if start_index == len(s):final.append(result.copy())returnfor i in range(start_index, len(s)):subset = s[start_index:i+1]if subset != subset[::-1]:continueelse:result.append(subset) #result里面其实存的还是i的索引，只不过是有选择地存储self.findValue(i+1, s, result, final)result.pop()returndef partition(self, s: str) -> List[List[str]]:start_index = 0result = []final = []self.findValue(start_index,s,result,final)return final

7. 复原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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

1. 和上面的题目一样的思路，只不过要熟练怎么把整型列表转换为字符串列表

str_list = [ str(i) for i in nums]

2. 有一个感受，第一个for循环，是树层的遍历，第二个递归，则是树枝的遍历。

8. 子集问题

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

1.观察树结构的过程，可以发现，这题和上面的分割不一样的是，最终结果是要收集每个中间阶段的结果，因此子集问题没有终止条件。
2. 一开始用的分割的方法，但是仔细梳理，这样的结果会是 [1], [2],[3]; [1], [1, 2] ,[3]; [1,2,3]。 会重复一次【1】和[3]

9. 子集问题II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

1. 和上面一题相比，这里的数组是有重复元素的。如果画二叉树结构可以看出来，需要进行去重；通过画二叉树过程可以看出，去重原理和上面的一样，都是树层去重，即i >start_index and nums[i]==nums[i-1] 为重复元素
2. 注意！！！！对nums进行排序，否则无法让重复元素站在一起。

10. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素 。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

1. 我犯了两个错误，1）这里求子序列，也就是不能sort数组，那就不能用原来的树层去重，而是用used = set()来记录树层是否用过。注意，used数组要放在for循环外面，保证每一树层的used数组互不干扰。
   if i > start_index and nums[i] == nums[i - 1]:
   continue
   2)if len(result) !=0: if nums[i] < result[-1]: continue
   这里注意应该是result[-1]而不是nums[i-1],因为nums[i-1]不一定被放到了result中。

class Solution:def findValue(self, start_index, nums, result, final):if len(result) >= 2:final.append(result.copy())used = set()for i in range(start_index, len(nums)):if len(result) !=0:if nums[i] < result[-1]:continueif nums[i] in used:continueresult.append(nums[i])used.add(nums[i])self.findValue(i+1, nums, result, final)result.pop()return def findSubsequences(self, nums: List[int]) -> List[List[int]]:start_index = 0result = []final = []self.findValue(start_index, nums, result, final)return final

11. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1. 解题思路是一样的，只不过排列问题的特殊点在于，used数组是全局的，而不是每层都是新的。这一点可以通过画二叉树图验证。由于是全局的used数组，因此在pop之后，还要设置used为False。
2. 由于没有重复元素，相当于只使用树枝去重就可以了。而树枝是从上到下的，因此used是全局的

class Solution:def findValue(self, nums, used, result, final):if len(result) == len(nums):final.append(result.copy())returnfor i in range(len(nums)):if used[i]==True:continueelse:result.append(nums[i])used[i]=Trueself.findValue(nums,used, result,final)result.pop()used[i]=Falsereturndef permute(self, nums: List[int]) -> List[List[int]]:used = [False] * len(nums)result = []final = []self.findValue(nums,used,result,final)return final

12. 全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

1. 由于多了重复元素，除了树枝去重外，还需要进行树层去重，每一层新建一个set()然后set.add()。注意树层去重，pop后并不会剔除，因为该层确定了之后不能再用这个元素。树枝去重则不同，需要进行False还原，因为下一个树枝还是会用到这些元素。

13. N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

1. 开始完全没有思路。主要是前面的题目都是给定一个一维数组，然后按照条件来输出结果。但是这里是二维数组，需要额外使用一个row来指定循环的层数。
2. 不能这样初始化二维数组，要用一个真值

board = [[]*n for _ in range(n)]#错误
board = [[.]*n for _ in range(n)] #正确

3. 由于是逐层选择，每次只需要对上一层的元素进行去重就可以了。分别对先前行的同一列，左上角和右上角进行去重Q

class Solution:def isValid(self, board, row, col,n):for i in range(row):if board[i][col] == "Q":return Falser = row-1c = col-1#左上对角线while r>=0 and c >=0:if board[r][c] == "Q":return Falser -=1c -=1#右上对角线r = row-1c = col+1while r>=0 and c <n:if board[r][c] == "Q":return Falser -=1c +=1return Truedef findValue(self, row, board,final,n):if row == n:final.append(["".join(row) for row in board]) ##注意这里中括号的位置returnfor col in range(n):board[row][col]="Q"if self.isValid(board, row, col,n):self.findValue(row+1, board, final,n)board[row][col] ="."else:board[row][col]="."returndef solveNQueens(self, n: int) -> List[List[str]]:board = [["."]*n for _ in range(n)]final = []row = 0self.findValue(row, board, final,n)return final

14. 解数独

1.和N皇后相比，N皇后一行只填一个，但是数独一行填N个，因此维度更高。关键在于，用了两个for循环，一个是列的for循环，挑选当前行的每一列的元素，一个是k的for循环，让当前元素选择n次。
2. isValid函数，先检查这个位置放是不是合法，如果合法就放下。
3. 使用了i的for循环，主要是考虑到如果某一行的数组全都是满的，如果没有i的for循环，就需要用

return self.findValue(board, row + 1, n) 

class Solution:def isValid(self, row, col, board, number):if number in board[row]:return Falsefor r in range(len(board)):if board[r][col] == number:return Falseleft_col = col- ((col)%3)left_row = row-((row%3))for r in range(left_row, left_row+3):for c in range(left_col, left_col+3):if board[r][c] == number:return Falsereturn Truedef findValue(self, board,n):for i in range(n):for j in range(n):if board[i][j] == ".":for k in range(1,10):if self.isValid(i,j,board,str(k)):#预判填了k之后board是否合法board[i][j] = str(k)result = self.findValue(board,n)if result:return True #下一级确定没问题，直接向上返回，跳出循环#如果下一级返回的是False,那恢复为.，自动进入下一个k循环，如果到了k的末尾，会自动返回False，因此不用额外设置条件            else:board[i][j] = "."return False        return True  #填充完毕，没有地方等于.,返回Truedef solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""n = len(board)self.findValue(board,n)

上面的代码超时了：

1. 对每一行建立一个列表，存储已经填充的数字；对每一列也建立一个列表，存储已经填充的数字；对每一个box建立一个列表，存储已经填充的数字
2. 建立一个待处理的事务列表，存储需要填充数字的坐标信息。

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:# 预存行、列、3×3 子方格的已填数字rows, cols, boxes = [set() for _ in range(9)], [set() for _ in range(9)], [set() for _ in range(9)]empty_cells = []  # 存储所有空白格的位置# **预处理**: 记录 board 里的数字，同时找到所有 "."for r in range(9):for c in range(9):if board[r][c] == ".":empty_cells.append((r, c))  # 记录空白格子else:num = board[r][c]rows[r].add(num)cols[c].add(num)boxes[(r // 3) * 3 + (c // 3)].add(num) #每个box存放9个数字# **回溯填充数独**def backtrack(index: int) -> bool:if index == len(empty_cells):  # **所有空白填完，返回 True**return Truer, c = empty_cells[index]  # 获取下一个空白格的位置box_id = (r // 3) * 3 + (c // 3)  # 计算当前格子属于哪个 3×3 方块for k in range(1, 10):num = str(k)if num not in rows[r] and num not in cols[c] and num not in boxes[box_id]:  # **判断是否可填**board[r][c] = numrows[r].add(num)cols[c].add(num)boxes[box_id].add(num)if backtrack(index + 1):  # **递归填下一个空白格**return True  # **成功填充数独**# **回溯**board[r][c] = "."rows[r].remove(num)cols[c].remove(num)boxes[box_id].remove(num)return False  # **如果 1-9 都无法填入，则回溯**backtrack(0)  # **从第 0 个空白格开始填**