Combination Sum

Intuition

Solution

from typing import List
from collections import defaultdict, deque


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.ans = []
        candidates.sort()
        self._helper(target, 0, candidates, [])
        return self.ans

    def _helper(self, target, start, candidates, path):
        if target == 0:
            self.ans.append(path[:])
            return
        elif target < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            self._helper(target - candidates[i], i, candidates, path)
            path.pop()