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

    def getCombination(self, i, need, stack):
        if need == 0:
            return [stack]
        output = []
        while i < len(self.candidates) and self.candidates[i] <= need:
            output += self.getCombination(i, need - self.candidates[i], stack + [self.candidates[i]])
            i += 1
        return output