< Back




216. Combination Sum III

We're asked to find all combinations of size k where the sum is equal to n, and we can't duplicate
numbers.

Using backtracking, we keep track of the number of numbers we've selected so far, the running sum,
and the running combination. For numbers in range 1 to 9, while we have less numbers than k - 1,
we select numbers where the running total + the currently selected number is less than n. We pass on
to the next iteration the next number in the range 1 to 9 - iteration while commence from there. We
also update the size and running total.

Once we're at size of chosen numbers == k - 1, there's only one number in the range that will
complete the combination, so we select the first one that sums with our running total to n, add it
to our answer, and immediately return.

The solution is as follows:


  class Solution:
      def combinationSum3(self, k: int, n: int) -> List[List[int]]:
          ans = []

          def backtrack(s: List[int], i: int, t: int, u: int) -> None:
              for j in range(i, 10):
                  if u < k - 1 and t + j <= n:
                      s.append(j)
                      backtrack(s, j + 1, t + j, u + 1)
                      s.pop()
                  elif t + j == n:
                      s.append(j)
                      ans.append(s[:])
                      s.pop()
                      return

          backtrack([], 1, 0, 0)

          return ans


_ Time Complexity:

  O((9! * k) / (9 - k)!) - Where k is the required size of the combination we're asked to create.

_ Space Complexity:

  O(k) - Where k is the size of the combination we're asked to create.