目录
润到递归了。下面是超级回溯大法！！！！！
思路：
使用回溯法解决问题----能够穷举所有解
回溯法框架：
参考缓缓神！
result=[]
def backtrack(选择列表,路径):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
#做选择
路径.add(选择)
将该选择从选择列表中移除
## 核心 递归调用之前【做选择】，调用之后【撤销选择】
backtrack(选择列表,路径)
#撤销选择
路径.remove(选择)
将该选择再加入选择列表
本题中（元素不可重复可复选）
如果不重复使用
控制range中的start元素即可
def backtrack(nums,start):
#每个结点的值都是一个子集，加入子集
-------
#对于选择列表中的每个选择
for i in range(start,len(nums)):
------
#递归
backtrack(nums,i+1)
----
return res
这个 i 从 start 开始，那么下一层回溯树就是从 start + 1 开始，从而保证 nums[start] 这个元素不会被重复使用
重复使用
把i+1改为i，就能无限生长下去
结束条件：路径和大target
代码：
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret=[]
def backtrack(candidates,path,target,start):
if sum(path)==target:
ret.append(path[:])
return
if sum(path)>target:
return
#如果还不够~，就继续dfs
for i in range(start,len(candidates)):
path+=[candidates[i]]
backtrack(candidates,path,target,i)
path.pop()
backtrack(candidates,[],target,0)
return ret
拓展1：元素无重复不可复选
nums中的元素是唯一的，每个元素只能被使用一次。组合问题为例，nums=[2,3,6,7]，和为7的组合只有[7]。
子集问题和组合问题都一样，大小为 k 的组合就是大小为 k 的子集。
子集问题：
按照离散数学，这不是求P(A)吗，拿手好戏！
在做全排列的过程中，本身就存在子集，只是我们并没有保存，如果在结束条件处略作修改，改为没有条件，每次节点的值本身就是子集，将其加入到结果中即可。但这样还存在重复，因为在全排列过程中可能会出现选择b作为开头但还可以选a，所以刚刚那样修改后结果会出现[a,b]，[b,a]，在集合中这二者是重复的。规避方式也很简单，每次从当前元素的下一个元素开始选。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ret=list()
#路径列表
track=list()
def backtrack(nums,start):
#每个结点值都是一个子集，加入子集
ret.append(track[:])
#对于选择列表中的每个选择
for i in range(start,len(nums)):
#选择
track.append(nums[i])
#递归
backtrack(nums,i+1)
#撤销选择
track.pop()
backtrack(nums,0)
return ret
组合问题：
翻译一下就变成子集问题了：给你输入一个数组 nums = [1,2..,n] 和一个正整数 k，请你生成所有大小为 k 的子集。
还是以 nums = [1,2,3] 为例，刚才78题让求所有子集，就是把所有节点的值都收集起来；现在只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：
在代码上，只是需要添加结束条件：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ret=[]
track=[]
def backtrack(n,start,k):
#结束条件，遍历到第k层就收工
if len(track)==k:
ret.append(track[:])
return
#对于所有的选择
#选择列表[1,2,---,n]
for i in range(start,n):
#选择
track.append(i)
#递归
backtrack(n,i+1,k)
#撤销选择
track.pop()
backtrack(n+1,1,k)
return ret
全排列问题：
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ret=[]
#选择列表为nums包含的元素
#used表示已经选择的数字
def backtrack(nums,path,used):
#结束条件
if len(path)==len(nums):
ret.append(path[:])
return
for i in range(len(nums)):
if used[i]:
#选过别回头
continue
#选择
path.append(nums[i])
used[i]=True
#递归
backtrack(nums,path,used)
#撤销选择
path.pop()
used[i]=False
#初始路径为空,used都为False
backtrack(nums,[],[False for _ in range(len(nums))])
return ret
拓展2：元素可重复不可复选
再--子集问题：
又类似于找P(A)，拿手好戏啊(bushi)
思路：
以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，写作 nums = [1,2,2']。显然，两条值相同的相邻树枝会产生重复，如都有2：[1,2]，[1,2']，所以需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：遍历了[1,2]就不再遍历[1,2']。
在代码实现上，先对nums进行排序，在遍历时如果当前元素nums[i]与前一个元素相等nums[i] == nums[i-1]则跳过该元素（注意越界问题）：
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
ret=list()
track=list()
#先排列
nums.sort()
def backtrack(nums,start):
#子集问题，不需要判断结束条件
ret.append(track[:])
#对于所有选择
for i in range(start,len(nums)):
#和上一个重复就跳过,i>start避免越界
if i>start and nums[i]==nums[i-1]:
continue
track.append(nums[i])
backtrack(nums,i+1)
track.pop()
backtrack(nums,0)
return ret
PS：
创建空列表
ret=[]
ret=list()感谢缓缓神！！
标签：backtrack,python,nums,List,ret,start,子集,刷题,总和 From： https://blog.csdn.net/m0_73629042/article/details/140550937