Combinations

Intro

Combination is a way of selecting items from a collection. The order of selection doesn't matter. For example, there's a collection of three fruits $\{apple, orange, pear\}$ for breakfast. You can only pick two of them. You can pick $\{apple, orange\}$, $\{apple, pear\}$, or $\{orange, pear\}$.

Question (LC.77)

Given two positive integers n and k, return all possible combinations of size k from [n].

Example

4 choose 2 (4, 2) =>
[ 
  [1,2], [1,3], [1,4],
  [2,3], [2,4],
  [3,4] 
]

4 choose 3 (4, 3) =>
[
  [1, 2, 3], 
  [1, 2, 4], 
  [1, 3, 4]
  [2, 3, 4]
]

What if n < 1 or k < 1 or n < k? Empty list How large is the input size? k is less than 10

Analysis

Finding all possible combinations requires an exhaustive search. Backtracking will be handy for enumeration problems like this. One thing worth noting is that the order does not matter for combinations. We want to use a strictly increasing order to eliminate duplicate combinations. For example, [1,2,3] can represent all other permutations from it [1,3,2], [2,1,3], [2,3,1], [3,1,2], etc. The order does not matter here because there's only one order.

Note: Strictly increasing is made possible by the condition that each integer/element can only be used at most once.

Approach

Step 1 Define recrusion
generate all combinations of size k starting with prefix comb
genComb(List<List<Integer>> results, List<Integer> comb, int n, int k, int cur)

Step 2 Recursive calls
for (int i = cur; i <= n; i++):
    comb.add(i)
    genComb(results, comb, n, k, i)
    comb.remove(last element)

Step 3 Base case
if (comb.size() == k):
    results.add(new comb)
    return

Code

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> results = new ArrayList<>();
    // edge check
    if (n < 1 || k < 0 || n < k) {
        return results;
    }
    // kick off the helper
    List<Integer> comb = new ArrayList<>();
    genComb(results, comb, n, k, 1);
    return results;
}

private void genComb(List<List<Integer>> results, 
                     List<Integer> comb, 
                     int n, 
                     int k, 
                     int cur) {
    // base case
    if (comb.size() == k) {
        results.add(new ArrayList<>(comb));
        return;
    }
    // recursive calls
    for (int i = cur; i <= n; i++) {
        comb.add(i);
        genComb(results, comb, n, k, i + 1); // each element can only be used once
        comb.remove(comb.size() - 1);
    }
}

Time Complexity

Time = #combinations * O(k) = O(n choose k) * O(k)