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)$


Comment