Combinations

MEDIUM✓ CHIP-TIMEDLC #77 — FULL STATEMENT ↗

The drill: Every group of k numbers you can choose from 1..n, order inside each group doesn't matter — return all of them.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two whole numbers, n and k, arrive. The numbers 1 through n form the pool, and the drill is to list every possible way to choose k of them.

This is a choosing problem, not an arranging one: [1, 2] and [2, 1] are the same group of two, so only one of them should ever show up in the output.

k never exceeds n, and every group is exactly size k — there's no requirement on which numbers get chosen beyond being distinct members of 1..n.

EX 01

n = 1 · k = 1

→ [[1]]

MINIMUM N AND K

EX 02

n = 4 · k = 2

→ [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

EX 03

n = 5 · k = 1

→ [[1], [2], [3], [4], [5]]

K = 1, EVERY ELEMENT ALONE

n and k are positive, with k no larger than n
n is kept small enough that C(n, k) groups can all be listed
each group holds exactly k distinct numbers from 1 to n
output order between groups and within a group is free

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

This is choosing, not arranging — [1, 2] and [2, 1] are the same group, so the algorithm should never produce both.

HINT 2 THE STRUCTURE

If a group only ever grows by picking numbers larger than the last one added, no group can ever be built twice in two different orders.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack with a start number: at each depth try every value from start to n, recurse with start = value + 1, and stop early once too few numbers remain to reach size k.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ASCENDING-ONLY CLIMBPATTERN · BACKTRACK, ASCENDING ONLYn = 3 · k = 2

STEP 1

n = 3, k = 2 — build every ascending pair. Growing a group only forward, never backward, means no pair is ever built twice.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/combinations.py — RACE PACE

LANG ▸

PACE ▸

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

        def backtrack(start):
            if len(path) == k:
                res.append(list(path))
                return
            for v in range(start, n + 1):
                if n - v + 1 < k - len(path):  # not enough numbers left to finish
                    break
                path.append(v)
                backtrack(v + 1)
                path.pop()

        backtrack(1)
        return res

TIME O(K·C(N,K))SPACE O(K)PYTHON · RACE PACE · 18 LN

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

TIME O(2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(n, k, 1, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int v = start; v <= n; v++) {
            if (n - v + 1 < k - path.size()) {
                break;
            }
            path.add(v);
            backtrack(n, k, v + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

TIME O(K·C(N,K))SPACE O(K)JAVA · RACE PACE · 22 LN

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> combo = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    combo.add(i + 1);
                }
            }
            if (combo.size() == k) {
                res.add(combo);
            }
        }
        return res;
    }
}

TIME O(2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED