Combinations

Problem

Return all combinations of k numbers chosen from 1..n.

Constraints

• 1 ≤ k ≤ n ≤ 20

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def combine(self, n, k):
        res = []
        def bt(start, cur):
            if len(cur) == k:
                res.append(cur[:]); return
            for i in range(start, n + 1):
                cur.append(i)
                bt(i + 1, cur)
                cur.pop()
        bt(1, [])
        return res

Java

import java.util.*;
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> out = new ArrayList<>();
        bt(out, new ArrayList<>(), 1, n, k);
        return out;
    }
    private void bt(List<List<Integer>> out, List<Integer> cur, int start, int n, int k) {
        if (cur.size() == k) { out.add(new ArrayList<>(cur)); return; }
        for (int i = start; i <= n - (k - cur.size()) + 1; i++) {
            cur.add(i);
            bt(out, cur, i + 1, n, k);
            cur.remove(cur.size() - 1);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.