#77 Combinations - Solution

The #77 Combinations problem asks you to generate all possible combinations of k numbers chosen from the range 1..n. The most effective strategy is backtracking, a technique that incrementally builds candidates and explores all valid possibilities.

Start with an empty path and recursively add the next possible number. At each step, choose a number, append it to the current combination, and continue exploring until the combination size reaches k. Once it does, record the combination and backtrack by removing the last element to explore other choices.

An important optimization is pruning the recursion when there are not enough remaining numbers left to reach size k. This avoids unnecessary exploration and improves performance.

The backtracking tree explores all valid selections of k elements from n, resulting in roughly C(n, k) combinations. The approach is efficient for generating combinations while maintaining manageable recursion depth.

Approach	Time Complexity	Space Complexity
Backtracking	O(C(n, k) * k)	O(k) recursion depth (excluding output)

Solutions (12)

Backtracking Approach

This method uses a backtracking technique, where we recursively build each combination by adding numbers incrementally and backtrack whenever we've constructed combinations of size k or cannot extend further.

Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time.
Space Complexity: O(k) due to the recursion stack storing the current combination.

C C++Java Python C#JavaScript

1def combine(n, k):
2    def backtrack(start, curr):
3        if len(curr) == k:
4            result.append(curr[:])
5            return
6        for i in range(start, n+1):
7            curr.append(i)
8            backtrack(i+1, curr)
9            curr.pop()
10
11    result = []
12    backtrack(1, [])
13    return result
14
15print(combine(4, 2))

Explanation

The Python implementation uses a local helper function backtrack to recursively explore possible combinations, leveraging Python's list's natural dynamic size for convenient management of the current list of numbers being explored.

Iterative Approach Using Bit Masking

Bit masking provides a novel way to generate combinations by representing choice decisions (e.g., pick or skip) in binary. A bit mask is applied to the set of numbers [1...n], and for each bit position, if the bit is set, that number is included in the combination.

Time Complexity: O(2ⁿ * n), as we iterate over all possible subsets of [1...n] and check the bit count.
Space Complexity: O(C(n, k) * k) for storing all combinations.

C C++Java Python C#JavaScript

1using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
        var result = new List<IList<int>>();
        int total = 1 << n;
        
        for (int mask = 0; mask < total; ++mask) {
            if (CountBits(mask) == k) {
                var current = new List<int>();
                for (int i = 0; i < n; ++i) {
                    if ((mask & (1 << i)) != 0) {
                        current.Add(i + 1);
                    }
                }
                result.Add(current);
            }
        }
        return result;
    }

    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    public static void Main(string[] args) {
        var solution = new Solution();
        var combinations = solution.Combine(4, 2);
        foreach (var combo in combinations) {
            Console.WriteLine("[{0}]", string.Join(", ", combo));
        }
    }
}