為什么不能暴力，因為不知道要循環多少次，如果長度為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
)
