Difficulty: Medium, Asked-in: Amazon, Adobe
Key takeaway: An excellent problem to understand the concept of problem-solving using backtracking and combinatorics. We can use similar ideas to solve other interview problems.
Given two numbers n and K and you have to find all possible combinations of K numbers from 1 to n.
Example
Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
Solution idea
We use the idea similar to the subset sum problem for creating possible combinations of K numbers from n numbers: we select each number from 1 to n and recur for two possible cases:
Suppose we have n = 4 and K = 2. The following tree diagram explains the generation of all combinations of size 2.
To implement this, All we need to do is to consider both cases and recursively create all possible combinations. Note: The idea of this approach comes from pascal’s Identity i.e: C(n, K) = C( n-1, K) + C(n-1, K-1) (Think!).
Suppose we use the function findKCombination(int K, int n), which returns output in a 2-D array. Inside the function, we declare two temporary arrays to store all outputs one by one:
Now we use a helper function kCombination(int output[][], int temp[], int index, int n, int i, int K) to generate and store all K combinations in the output array using temp array. Here we also use a parameter index for excluding or including the current element in the combination and a parameter i for tracking the current element of the combination. Note: Our initial call is kCombination(output, temp, 0, n, 0, K).
Solution pseudocode C++
vector<vector<int>> findKCombination(int K, int n)
{
vector<vector<int>> output
vector<int> temp(K,0)
kCombination(output, temp, 0, n, 0, K)
}
void kCombination(vector<vector<int>> output,
vector<int> temp, int index, int n, int i, int K)
{
if (index == K)
{
output.push_back(temp)
return
}
if (i >= n)
return
temp[index] = i + 1
kCombination(output, temp, index + 1, n, i + 1, K)
kCombination(output, temp, index, n, i + 1, K)
}
Solution analysis
Here for each element, there are two possibilities i.e; whether the element will be selected or not. This creates two cases for each element and we are going to iterate for all n elements. So, the overall time complexity will be O(2^n). (Think!)
Critical ideas to think!
Solution idea
The idea is to generate a combination tree where we fix each number from 1 to n and recursively build the combination of K numbers. Suppose we have n = 5 and K = 3.
To implement this:
Solution pseudocode C++
vector<vector<int>> findKCombination(int K, int n)
{
vector<vector<int>> output
vector<int> temp(K,0)
kCombination(output, temp, 0, 0, n, K)
}
void kCombination(vector<vector<int>> output,
vector<int> temp, int index , int start, int end, int K)
{
if (index == K)
{
output.push_back(temp)
return
}
for (int i = start; i < end && end - i + 1 >= K - index; i = i + 1)
{
temp[index] = i + 1
kCombination(output, temp, index + 1, i + 1, end, K)
}
}
Solution analysis
The loop in the algorithm will run C(n, K) times as this is the possible number of combinations and in each iteration, Elements can get selected in the range of (n-K) as K elements are already selected and we just replacing elements which are already occupied. So, the overall time complexity will be O(C(n, K) * (n-K)).
Space complexity = O(K* C(n, K)) (as we have total C(n, K) possible answer each having a size of K)
Critical ideas to think!
Solution idea
In this approach, we are using the power of DFS to recursively iterate through the range to generate all possible combinations. The iteration steps of the DFS approach are similar to the second approach we discussed above.
Here we iterate until we get a set consisting of K elements and store that subset in our resultant vector and then we backtrack and remove the previous element inserted in our temporary vector and consider further elements from the range which are not considered. This way all combinations are generated.
Solution pseudocode C++
vector<vector<int>> findKCombination(int K, int n)
{
vector<vector<int>> output
vector<int> temp(K,0)
kCombination(output, temp, 1, n, K)
}
void kCombination(vector<vector<int>> output,
vector<int> temp, int index ,int n, int K)
{
if (K == 0)
{
output.push_back(temp)
return
}
for (int i = index; i <= n, i = i + 1)
{
temp.push_back(i)
kCombination(output, temp, i + 1, n, K - 1)
temp.pop_back(i)
}
}
Solution analysis
for loop can run for a maximum of n times with each backtrack with the maximum iteration of NcK times. i.e: overall time complexity will be O(N* C(n, K)).
Space Complexity = O(k* C(n, K))(as we have total C(n, K) possible answer each having a size of k )
Critical ideas to think!
Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!
Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!