#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

1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5    public List<List<Integer>> combine(int n, int k) {
6        List<List<Integer>> result = new ArrayList<>();
7        backtrack(n, k, 1, new ArrayList<>(), result);
8        return result;
9    }
10
11    private void backtrack(int n, int k, int start, List<Integer> current, List<List<Integer>> result) {
12        if (current.size() == k) {
13            result.add(new ArrayList<>(current));
14            return;
15        }
16        for (int i = start; i <= n; ++i) {
17            current.add(i);
18            backtrack(n, k, i + 1, current, result);
19            current.remove(current.size() - 1);
20        }
21    }
22
23    public static void main(String[] args) {
24        Solution solution = new Solution();
25        List<List<Integer>> combinations = solution.combine(4, 2);
26        for (List<Integer> combo : combinations) {
27            System.out.println(combo);
28        }
29    }
30}

Explanation

The Java implementation relies on the ArrayList class for dynamic array handling, with the backtrack method recursively forming combinations, similar to how it's done in C++.

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

1#include <vector>

std::vector<std::vector<int>> combine(int n, int k) {
    std::vector<std::vector<int>> result;
    int total = 1 << n;

    for (int mask = 0; mask < total; ++mask) {
        if (__builtin_popcount(mask) == k) {
            std::vector<int> current;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    current.push_back(i + 1);
                }
            }
            result.push_back(current);
        }
    }
    return result;
}

int main() {
    int n = 4, k = 2;
    std::vector<std::vector<int>> combinations = combine(n, k);
    for (const auto& combo : combinations) {
        std::cout << "[";
        for (size_t i = 0; i < combo.size(); ++i) {
            std::cout << combo[i];
            if (i < combo.size() - 1) std::cout << ", ";
        }
        std::cout << "]\n";
    }
    return 0;
}