Combinations - Interview Problem
Difficulty: Medium
Asked in: Amazon, Adobe
Understanding The Problem
Problem Description
Given two integers
n
and
k
, write a program to return all possible combinations of
k
numbers out of
1 2 3 ... n
.
Problem Note
- Elements in a combination must be in a non-descending order.
- The combinations themselves must be sorted in ascending order, i.e., the combination with the smallest first element should be printed first.
-
The combination
[1,2]
is valid but[2,1]
is invalid as2>1
.
Example 1
Input: n = 3, k = 2
Output:
[
[1,2],
[1,3],
[2,3]
]
Example 2
Input: n = 5, k = 3
Output:
[
[1 2 3],
[1 2 4],
[1 2 5],
[1 3 4],
[1 3 5],
[1 4 5],
[2 3 4],
[2 3 5],
[2 4 5],
[3 4 5]
]
You may try this problem here.
Solution
This problem is a famous backtracking problem.
You might have understood what’s happening while looking over the examples. Let’s take an example, given k is 2, that means we have to generate combinations of length 2 and the set of numbers we have are from 1 to n, in this case, n is 4. We will solve this problem by using a backtracking approach.
The call stack will be:
N = 4, K = 2.
backtrack(1, [])
backtrack(2, [1])
backtrack(3, [1, 2])
backtrack(4, [1, 3])
backtrack(5, [1, 4])
backtrack(3, [2])
backtrack(4, [2, 3])
backtrack(5, [2, 4])
backtrack(4, [3])
backtrack(5, [3, 4])
backtrack(5, [4])
If you will look at the above stack, you’ll see how the functions can be calling itself until the
current combination
array length becomes equal to
k
. As soon as it touches the length
k
, it starts to backtrack to the previous state. If there are not enough elements in the
current combination
, it will run through fisrt~N and append all the element
num
to the
combination
, and set the
first
to
num+1
.
In other words, if we have used 3, we will not use 3 and the number below 3 anymore.
We will create a result array to store the generated combinations, we can append the combinations each time its length becomes equal to
k
. While backtracking or going to the previous state, we will pop out the last element of the
current combination
array. The popped out element represents, we have checked all the possible combinations with that prefix array and we are ready to explore the possible combinations with elements greater than popped element.
Solution Steps
-
Create a
backtrack
function, which will search for all possible combinations of lengthk
from the set of numbers 1 to n. -
Pass a parameter
start
in the backtrack function which will tell the backtrack function from where to look for the elements. -
For each value of
i
in the rangestart
ton
, appendi
in the current combination sequence and look for the rest of the elements that needed to be filled in thecurr_comb
. If all possible combinations have been explored, then pop out thati
and explore the rest possible sequences -
Whenever the
curr_comb
sequence becomes the length ofk
, append it to the finalcombs
array.
Recursive Pseudo Code
int[][] combine(int n, int k) {
int[][] combs
int[] curr_comb
backtrack(combs, curr_comb, 1, n, k);
return combs;
}
void backtrack(int[][] combs, int[] curr_comb, int start, int n, int k) {
if(k is 0) {
combs.add(curr_comb)
return
}
for(int i=start to i<=n) {
curr_comb.add(i)
backtrack(combs, curr_comb, i+1, n, k-1)
curr_comb.remove(curr_comb.size() - 1)
}
}
The above approach could also be molded into an iterative approach.
The idea is to iteratively generate combinations for all lengths from 1 to k. We start with a list of all numbers
<= n
as combinations for
k == 1
. When we have all combinations of length
k-1
, we can get the new ones for a length
k
with trying to add to each one all elements that are
<= n
and greater than the last element of a current combination.
Iterative Pseudo Code
int[][] combine(int n, int k) {
if (k is 0 or n == 0 or k > n)
return []
int[][] combs
for (int i = 1 to i <= n)
combs.add([i])
for (int i = 2 to i <= k) {
int[][] newCombs
for (int j = i to j <= n) {
for (int[] comb in combs) {
if (comb[comb.size()-1] < j) {
newComb = comb
newComb.add(j)
newCombs.add(newComb)
}
}
}
combs = newCombs
}
return combs
}
Complexity Analysis
Time Complexity: O(n!/k!(n-k)!), or mathematically
n
choose
k
.
Recursive Space Complexity: O(n!/k!(n-k)!)
Iterative Space Complexity: O(n²)
Critical ideas to Think!
- Do you think that the time complexity for iterative and recursive approaches would be the same?
- Can you draw a recursive tree diagram following the recursive approach for Example 2 mentioned above?
-
In curr_comb.remove(curr_comb.size() — 1)
Why do we remove the last one?
Considering Example 1, if you want to get [1,3] after you had got [1,2], there is no need to create another list, you just need to remove ‘2’ — that is the
curr_comb.size()-1
.
- How did we "backtrack" in this approach?
- Can you mathematically explain the time complexity?
Suggested Problems To Solve
- Combination sum
- Permutations
- Sudoku Solver
- Rat in a maze
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding!
Enjoy Algorithms!