Leetcode 【39、40、77】

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def search(tar):
            for c in candidates:
                if a[-1] <= c:  # 组合数
                    a.append(c)
                    tar -= c
                    if tar == 0:
                        ans.append([])
                        for n in a:
                            ans[-1].append(n)
                        ans[-1].pop(0)  # 把前面的一个0去掉
                    elif tar > 0:
                        search(tar)
                    a.pop()  # 恢复，回溯一步
                    tar += c  # 恢复，回溯一步
                        
        ans = []
        a = [0] # 防止下标越界
        search(target)
        return ans

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def search(tar):
            for k, v in enumerate(candidates):
                if not b[k] and a[-1] <= v:
                    a.append(v)
                    b[k] = True
                    tar -= v
                    if tar == 0:
                        tem = []
                        for n in a:
                            tem.append(n)
                        tem.pop(0)
                        if tem not in ans:  # 去重
                            ans.append(tem)
                    elif tar > 0:
                        search(tar)
                    a.pop()
                    b[k] = False
                    tar += v     
        
        a = [0]
        b = [False] * len(candidates)
        ans = []
        search(target)
        return ans

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def search(ind, r, path):
            for i in range(ind, n+1):
                path += [i]
                if r == k:
                    ans.append(path[:])  # 注意这里传引用调用，不然path变化ans也会改变
                else:
                    search(i+1, r+1, path)
                path.pop()
                
        ans = []
        search(1, 1, [])
        return ans