#回溯
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(target,ans,combine,idx):
            if idx == n:
                return
            if target == 0:
                ans.append(list(combine))
                return
            #跳过idx
            dfs(target,ans,combine,idx+1)
            #选择idx
            if target-candidates[idx] >= 0:
                combine.append(candidates[idx])
                dfs(target-candidates[idx],ans,combine,idx)
                combine.pop()
            
            

        n = len(candidates)
        ans = []
        combine=[]
        dfs(target,ans,combine,0)
        return ans