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.