为什么不能暴力，因为不知道要循环多少次，如果长度为n，难道要循环n次么，回溯的本质还是暴力，但是是可以知道多少层的暴力
之所以要pop是因为回溯相当于一个树形结构，要pop进行第二个分支
剪枝：如果剩余的数字个数 < 还需要的个数，那这一支就没必要继续了（不可能凑满 k）。比如77
固定数量
77. 组合 - 力扣（LeetCode）
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""result=[]path=[]def backtracking(n,k,start):
#当你将 path 添加到 result 时，如果不使用 copy()，实际添加的是 path 的引用,就是添加的不是中间的状态if len(path)==k:result.append(path.copy())return i=startwhile i<=n and n-i+1>=k-len(path):path.append(i)backtracking(n,k,i+1)path.pop()i=i+1backtracking(n, k, 1)return result可以重复选取+不固定数量+固定目标值
39. 组合总和 - 力扣（LeetCode）
class Solution:#与77组合区别在于树结构迭代时，不是start+1，因为start对应的数字还能再取def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result=[]path=[]def backtracking(candidates,target,start):if(sum(path)>target):returnif(sum(path)==target):result.append(path.copy())returni=startwhile((i<len(candidates))):path.append(candidates[i])backtracking(candidates,target,i)path.pop()i=i+1backtracking(candidates,target,0)return result固定数量+固定目标值
216. 组合总和 III - 力扣（LeetCode）
class Solution(object):def combinationSum3(self, k, n):""":type k: int:type n: int:rtype: List[List[int]]"""result=[]path=[]target=nnum=kstart=1end=9currentsum=0#这里可以定义一下currentsum，否则复杂度又上升了def backtracking(target,num,path,start,end,currentsum):#退出条件and不要忘记len(path)==num的条件if currentsum==target and len(path)==num:#result.append(path)不可以这样，加入的是引用result.append(path.copy())returnif currentsum>target:return#path.pop()回溯操作可以统一位置for i in range(start,end+1):path.append(i)currentsum+=i#num-=1 这是全局变量不需要变化backtracking(target,num,path,i+1,end,currentsum)path.pop()currentsum-=i#num+=1backtracking(target,num,path,start,end,currentsum)return result
)
