Combinations

Given n and k, return all combinations of k numbers chosen from 1 to n. Each combination is in increasing order, and the combinations are listed in lexicographic order.

LeetCode: 77. Combinations

Example

Text

n = 4, k = 2  ->  [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]

There are C(n, k) = n! / (k! (n - k)!) combinations.

Brute force: filter all subsets

Generate every subset of 1 to n with a bitmask and keep those with exactly k elements.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> out = new ArrayList<>();
        // Masks run in increasing order. Bit v-1 stands for number v, so the lowest
        // number is the least significant bit. Sort afterwards for lexicographic order.
        for (int mask = 0; mask < (1 << n); mask++) {
            if (Integer.bitCount(mask) != k) continue;
            List<Integer> combo = new ArrayList<>();
            for (int v = 1; v <= n; v++) {
                if ((mask & (1 << (v - 1))) != 0) combo.add(v);
            }
            out.add(combo);
        }
        out.sort((a, b) -> {
            for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
                int c = Integer.compare(a.get(i), b.get(i));
                if (c != 0) return c;
            }
            return Integer.compare(a.size(), b.size());
        });
        return out;
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2));
    }
}

Output

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

Time: O(2ⁿ · n), however small C(n, k) is: n = 20, k = 2 checks a million masks for 190 answers. Space: O(C(n, k) · k) for the output.

Optimal: backtracking with pruning

Choose the numbers in increasing order: after choosing v, the next number starts at v + 1. Also stop early when there aren't enough numbers left: if need more numbers are required, the next choice can be at most n - need + 1.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> out) {
        int need = k - current.size();
        if (need == 0) {
            out.add(new ArrayList<>(current));
            return;
        }
        for (int v = start; v <= n + 1 - need; v++) {
            current.add(v);
            backtrack(v + 1, n, k, current, out);
            current.remove(current.size() - 1); // remove by index, not by value
        }
    }

    static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> out = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(k), out);
        return out;
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2));
        System.out.println(combine(3, 3) + " " + combine(20, 2).size());
        System.out.println(combine(3, 0) + " " + combine(3, 5));
    }
}

Output

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
[[1, 2, 3]] 190
[[]] []

Time: O(C(n, k) · k): with the pruning, every call leads to at least one combination. Space: O(k) besides the output.

current.remove(current.size() - 1) removes by index. current.remove(v) on a List<Integer> would also compile, but it would remove the element at index v, not the value v.

Edge cases

k = 0: one combination, the empty one.
k = n: one combination, all the numbers.
k > n: no combinations. The loop bound n + 1 - need is below start, so the loop body never runs and the result is empty.