Combinations

NeetCode: Combinations · LeetCode: 77. Combinations · Difficulty: Medium

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The answer may be returned in any order.

Example

Text

Input:  n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

The brute force sorts its result with a comparator before returning, because bitmask order is not lexicographic. The backtracking version produces the lexicographic order by construction.

Brute force: generate all subsets, keep those of size k

Enumerate all 2^n subsets with an int bitmask and keep the ones with exactly k bits set. Integer.bitCount counts the set bits. The shift 1 << n fits in an int for the problem's limit of n <= 20.

Java

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

public class Main {
    static class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> result = new ArrayList<>();
            for (int mask = 0; mask < (1 << n); mask++) {
                if (Integer.bitCount(mask) == k) {
                    List<Integer> combo = new ArrayList<>();
                    for (int i = 0; i < n; i++) {
                        if ((mask >> i & 1) == 1) {
                            combo.add(i + 1);
                        }
                    }
                    result.add(combo);
                }
            }
            result.sort(Main::compare);
            return result;
        }
    }

    // Lexicographic order of two lists, used to keep the results in a fixed order.
    static int compare(List<Integer> a, List<Integer> 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());
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.combine(4, 2));
        System.out.println(sol.combine(1, 1));
        System.out.println(sol.combine(3, 3));
    }
}

Output

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

All 2^n subsets are examined even though only C(n, k) of them matter. Time: O(n * 2^n). Space: O(C(n, k) * k) for the output.

Optimal: backtracking that only builds size-k subsets

Choose numbers in increasing order. The path is an ArrayList<Integer>, and path.remove(path.size() - 1) removes by index, so it takes off the last element. start is the smallest number that may be picked next, so each combination is generated exactly once (never as several permutations of the same set). Stop as soon as the current path has k numbers.

Pruning: if need = k - path.len() more numbers are required, the last valid starting number is n - need + 1. Beyond that there are not enough numbers left, so the loop stops there and every branch of the recursion ends in a valid answer.

Java

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

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

        private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> out) {
            if (path.size() == k) {
                out.add(new ArrayList<>(path));
                return;
            }
            int need = k - path.size();
            // the last usable start is n - need + 1
            for (int x = start; x <= n - need + 1; x++) {
                path.add(x);
                backtrack(x + 1, n, k, path, out);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.combine(4, 2));
        System.out.println(sol.combine(1, 1));
        System.out.println(sol.combine(3, 3));
    }
}

Output

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

The answer has C(n, k) combinations of length k, so this matches the output size. Time: O(k * C(n, k)). Space: O(k) recursion depth, not counting the output.