combine.py

from typing import List
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                # make a deep copy of the current combination
                results.append(list(comb))
                return
            elif remain < 0:
                # exceed the scope, stop exploration.
                return

            for i in range(start, len(candidates)):
                # add the number into the combination
                comb.append(candidates[i])
                # give the current number another chance, rather than moving on
                backtrack(remain - candidates[i], comb, i)
                # backtrack, remove the number from the combination
                comb.pop()

        backtrack(target, [], 0)

        return results


# Checking test cases:
if __name__ == '__main__':
    Sol = Solution()
    Solve = Sol.combinationSum([2,3,6,7], 7)  # [3, 9] -> [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    Solve_2 = Sol.combinationSum([2,3,5], 8)  # [3, 9] -> [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    print(Solve)
    print(Solve_2)