combination_sum.py

class Solution:
    def combinationSum(self, candidates, target):
        if not candidates:
            return []

        result = []

        def backtrack(solution, idx, curr_sum):
            if curr_sum == target:
                result.append(solution[:])
                return

            if idx == len(candidates) or curr_sum > target:
                return

            # choose
            solution.append(candidates[idx])
            backtrack(solution, idx, curr_sum + candidates[idx])
            solution.pop()

            # don't choose
            backtrack(solution, idx + 1, curr_sum)

        backtrack([], 0, 0)
        return result


if __name__ == "__main__":

    solution = Solution()

    candidates = [2, 3, 6, 7]
    target = 7
    result = solution.combinationSum(candidates, target)
    assert result == [[2, 2, 3], [7]]
    print(result)
    print("Test Case 1 Passed!")