https://leetcode.com/problems/combination-sum

This is classical backtracking problem, so let us use BackTr(target, curr_sol, k) function, where:

  1. target is target we need to build, if we get some number, we subtract if from target.
  2. curr_sol is current solution built so far.
  3. k is index in our candidates: each new number we take should have number more or equal than k.

So, no in algorighm we do:

  1. If target == 0, it means we found solution, which is kept in curr_sol, so we add it to self.sol list of all found solutions.
  2. If target if negative or k is more than number of candidates, we need to go back.
  3. Finally, for each candidate index in k,..., we run our function recursively with updated parameters.

Complexity: TBD

class Solution:
    def combinationSum(self, candidates, target):
        def BackTr(target, curr_sol, k):  
            if target == 0:
                self.sol.append(curr_sol)

            if target < 0 or k >= len(candidates):
                return

            for i in range(k, len(candidates)):
                BackTr(target - candidates[i], curr_sol + [candidates[i]], i)
        
        self.sol = []
        BackTr(target, [], 0)   
        return self.sol

If you like the solution, you can upvote it on leetcode discussion section: Problem 0039