Reference: LeetCode EPI 15.6
Difficulty: Medium

Problem

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

Example: 

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Analysis

Backtracking

Reference: LeetCode Solution

One brute-force approach is to compute all subsets of ${1,2,\ldots, n}$, and then restrict the result to subsets of size $k$. It computes all subsets though, which takes $O(n 2^n)$ time regardless of $k$.

Take ${1, 2, 3, 4}$ and $k = 3$ as an example.

We use a more focused approach. We make use of case analysis. There are two possibilities for a subset—it does not contains $1$, or it does contains $1$. In the first case, we return all subsets of size $k$ of ${2, 3, 4}$; in the second case, we compute all $(k - 1)$ sized subsets of ${2, 3, 4}$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// The variables name correspond to the ones in code.
Example: [1, 2, 3, 4]
d = 1
  i = 1
    pick 1 from [1,2,3,4]
    call (n, k, d = i + 1 = 2) subproblem of picking 2 elements from [2,3,4]
    remove 1
  i = 2
    pick 2 from [1,2,3,4]
    call (n, k, d = i + 1 = 3) subproblem of picking 2 elements from [3,4] --> One Instance
    remove 2
  i = 3
    pick 3 from [1,2,3,4]
    call (n, k, d = i + 1 = 4) subproblem of picking 2 elements from [4] --> Impossible
    remove 3
  i = 4
    pick 4 from [1,2,3,4]
    call (n, k, d = i + 1 = 5) subproblem of picking 2 elements from [] --> Impossible
    remove 4

See the example above. We can handle the impossible cases by comparing the number of remaining choices with the $(k - \text{number of picked elements})$. For example, when d = 1, i = 3, we call (n, k, d = i + 1 = 4), the remaining number of elements equals n - i + 1 = 4 - 4 + 1 = 1, which is less than k - pickedList.size() = 3 - 1 = 2.

In the base case above, we should return right away without updating the result list. However, there exists another base case when k == pickedList.size(). In this case, we should copy the current list and put it into the result list.

Note: The idea is not difficult, but how we implement it is challenging since we should consider what parameters we need in the recursive function.

  • In my version, n and k are not changing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> combine(int n, int k) {
  List<List<Integer>> result = new ArrayList<>();
  List<Integer> nums = new ArrayList<>();
  combine(n, k, 1, nums, result);
  return result;
}

private void combine(int n, int k, int d, List<Integer> nums, List<List<Integer>> result) {
  // base case
  if (n - d + 1 < k - nums.size()) { // remaining elements are not enough
    return;
  }
  if (nums.size() == k) { // get a result
    result.add(new ArrayList<>(nums));
    return;
  }
  
  for (int i = d; i <= n; ++i) {
    nums.add(i);
    combine(n, k, i + 1, nums, result);
    nums.remove(nums.size() - 1); // remove the last
  }
}

Time: $O(k C^k_N)$, where $C^k_N = \frac{N!}{(N-k)!k!}$.
Space: $O(k C^k_N)$