Problem Statement in English

You’re given two integers n and k. You need to return all possible combinations of k numbers out of the range [1, n].

Approach

There are 2 approaches to this. The first uses an inclusion-exclusion principle, and the second an approach that resembles actual $\binom{n}{k}$ style calculations, which is more efficient.

Inclusion-Exclusion Principle

At each index, we have the option to either include the number at that index in our current combination or exclude it. We can use a recursive function to explore both possibilities, and when we reach a combination of size k, we add it to our result list.

$\binom{n}{k}$ Style Calculation

In this approach, we start from the first number and try to build combinations by adding subsequent numbers. We keep track of the current index of the array we’re at, and only consider indices that are greater than the last one in the current combination.

When the size of the built combination reaches k, we add it to our result list. This method is more efficient as it avoids unnecessary recursive calls by only considering valid numbers for the current combination.

And we’re done.

Solution in Python

  • Unoptimised $O(k \cdot 2^k)$ solution using DFS

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

        buffer = []
        space = [i for i in range(1, n+1)]
        ans = []

        def dfs(i):
            if len(buffer) == k:
                ans.append(buffer[:])
                return
            if i >= n:
                return

            buffer.append(space[i])
            dfs(i+1)
            buffer.pop()

            dfs(i+1)

        dfs(0)

        return ans
  • Optimised $O(k \times \binom{n}{k})$ solution using DFS

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        res = []
        def helper(i, curComb):
            if len(curComb) == k:
                res.append(curComb.copy())
                return
            if i > n:
                return

            for j in range(i, n + 1):
                curComb.append(j)
                helper(j + 1, curComb)
                curComb.pop()

        helper(1, [])
        return res

And we are done.