39. Combination Sum

class Solution: def helper(self, candidates, chosen, res, remaining, last_choice_idx): """ @candidates: the candidate coins @chosen: already chosen sequence @res: vector to store all results @remaining: remaining money to choose @last_choice_idx: important! the index of candidates that we choose last time. Use to control no duplication. """ if (remaining == 0): res.append(chosen.copy()) return for idx in range(last_choice_idx, len(candidates)): # choose coin = candidates[idx] chosen.append(coin) remaining -= coin # backtracking if (remaining < 0): # unchoose chosen.pop(-1) remaining += coin continue # explore self.helper(candidates, chosen, res, remaining, idx) # unchoose chosen.pop(-1) remaining += coin def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ chosen = [] res = [] self.helper(candidates, chosen, res, target, 0) return res