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\}$.

Formula Derivation

Question (LC.77)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example

4 choose 2 (n = 4, k = 2)
[ 
  [1,2], [1,3], [1,4],
  [2,3], [2,4],
  [3,4]
]

4 choose 3
list = [1, 2, 3, 4]
[
  [1, 2, 3], 
  [1, 2, 4], 
  [1, 3, 4]
  [2, 3, 4]
]

Analysis

To break down this problem, we want to perform a dfs/recursion on the given list[1...n]

find all combinations of size 3, start from number 1
combineDFS(n, k = 3, startNum = 1, combination{})
    find all combinations of size 2, start from number 2
    combineDFS(n, k = 2, startNum = 2, combination{1})
        find all combination of size 1, start from number 3
        combineDFS(n, k = 1, startNum = 3, combination{1, 2})
            k = 0, results.add({1, 2, 3}), end
        find all combiantion of size 1, start from number 4
        combineDFS(n, k = 1, startNum = 4, combination{1, 2})
            k = 0, results.add({1, 2, 4}), end
        combineDFS(A, size = 0, startIndex = 4, combination{1, 2, 4}) end
    find all combinations of size 2, start from number 3
    combine(n, k = 2, startNum = 3, combination{1})
        ... end with {2, 3, 4}, backtrack to top level
find all combinations of size 3, start from number 2
combineDFS(n, k = 3, statNum = 2, combination{})

Approach

1. Define the recursion

   • function find all combinations (size k) START with input combination
   • parameters (n, k, results, startNum, combination)
   • return values void, add combinations of size k to results

2. DFS

   for i from startIndex to n
    previsit: combination.add(i)
    combineDFS(n, k-1, results, i+1, combination)
    postvisit: combination.remove(combination.size() - 1)
   end for
   

3. Stop conditions

   if (k == 0)
    results.add(new ArrayList<>(combination))
    return;
   

Code

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> results = new ArrayList<>();
    if (k > n) {
        return results;
    }
    // find all combinations of size k start from nothing
    combineDFS(n, k, results, 1, new ArrayList<>());
    return results;
}
private void combineDFS(int n, int k, List<List<Integer>> results, 
                        int startNum, List<Integer> combination) {
    // stop condition
    if (k == 0) {
        results.add(new ArrayList<>(combination));
        return;
    }
    // DFS
    for (int num = startNum; num <= n; num++) {
        combination.add(num);
        combineDFS(n, k - 1, results, num + 1, combination);
        combination.remove(combination.size() - 1);
    }
}

Time Complexity

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