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

If in problem we need to return all possible options with some property, usually it means that we need to do backtracking. Let us use BackTr function with parameters:

  1. k is number of numbers we need to take to build our number.
  2. n is number we need to build
  3. curr_sol built solution so far.

Then if n<0 of k<0 we need to go back; if n==0 and k==0 means that we found solution, so we add it to our self.sol. Then we just run our BackTr with parameters: k-1: we need to take one less number, n-i, where i is the last digit we added: it is either starts with 1 or with curr_sol[-1] + 1 and curr_sol + [i] will be our built solution so far.

Finally, we run ` self.BackTr(k, n, []) and return self.sol`.

Comlexity: For first digit we have not more than 9 options, for second one no more than 8 and so on, so there will be 9*8*...*(9-k+1) possible options, for each of which we need O(k). We can improve this bound if we take into account that there is 2^9 possible combinations at all, so complexity is O(2^9*k), because of all dead-ends we can have. Space complexity is O(k), if we do not take into account output solution.

class Solution:
    def combinationSum3(self, k, n):
        self.sol = []
        self.BackTr(k, n, [])
        return self.sol
        
    def BackTr(self, k, n, curr_sol):
        if n < 0 or k < 0: return
        if n == 0 and k == 0:
            self.sol.append(curr_sol)
            
        start = curr_sol[-1] + 1 if curr_sol else 1
            
        for i in range(start, 10):
            self.BackTr(k - 1, n - i, curr_sol + [i])

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