Combinations

How it works

Each subset of numbers from 1 to n can be represented as an n-bit binary number, where bit i being set means number (i+1) is included. We iterate through all possible bitmasks and keep only those with exactly k bits set.

Steps

1. Iterate through all integers from 0 to 2^n - 1. Each integer represents a possible subset.
2. For each mask, extract the numbers corresponding to set bits (if bit j is set, include j + 1).
3. If the resulting subset has exactly k elements, add it to the result.
4. Return all valid combinations.

Complexity

• Time complexity: O(n * 2 ^ n)
• Space complexity: O(k * frac {n!}{(n - k)! * k!}) for the output array.

Where n is the number of elements and k is the number of elements to be picked.

Things to watch for

Forgetting to Copy the Combination Before Adding to Results

When adding the current combination to the result list, you must create a copy. Otherwise, subsequent modifications during backtracking will alter the already-added result.

Missing the Backtrack Step

After exploring a branch with an element included, you must remove it before exploring the next branch. Forgetting to pop leads to combinations with too many elements.

Using Wrong Loop Bounds

Starting the loop at 0 instead of start causes duplicate combinations like [1,2] and [2,1]. The loop must start from the current position to ensure each combination is generated only once in sorted order.

from typing import List
from math import comb

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        for mask in range(1 << n):
            comb = []
            for bit in range(n):
                if mask & (1 << bit):
                    comb.append(bit + 1)

            if len(comb) == k:
                res.append(comb)
        return res

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        for (int mask = 0; mask < (1 << n); ++mask) {
            vector<int> comb;
            for (int bit = 0; bit < n; ++bit) {
                if (mask & (1 << bit)) {
                    comb.push_back(bit + 1);
                }
            }
            if (comb.size() == k) {
                res.push_back(comb);
            }
        }
        return res;
    }
};