< Back




77. Combinations

We're given n and k, n represents the range of numbers for [1, n) and k represents the number of
numbers we'll choose for a combination. Our goal is to return all possible combinations possible
for n choose k. They can be unordered, however, the contents can't be duplicates, either.

We use backtracking, again, treating each combination as a part of a graph. We recurse with a base
case of checking if the candidate subset of characters is length k - if so we add it to the answer
and return.

We pass the index of the range in [1, n) to each level of recursion to maintain our space from where
we push / pop numbers onto the candidate subset. At each stage, we calculate the remaining numbers
we need to choose for a combination, and the count of available numbers to choose from. This
optimization enables us to avoid traversing paths of the graph that won't produce combinations.

The solution is as follows:


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

          def backtrack(s: List[int], i: int) -> None:
              if len(s) == k:
                  ans.append(s[:])
                  return

              need = k - len(s)
              remain = n - i + 1
              available = remain - need

              for j in range(i, i + available + 1):
                  s.append(j)
                  backtrack(s, j + 1)
                  s.pop()

          backtrack([], 1)

          return ans


_ Time Complexity:

  O(n! / ((k - 1)! * (n - k)!)) - Well studied problem in combinatorics, you can get this time
  complexity and the breakdown of the math from wikipedia.

_ Space Complexity:

  O(k) - This is the max number of integers we maintain in our combinations.