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.
Input: n = 4, K = 2
Output: [ [1 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4] ]
Explanation: We need to select all possible combinations of K numbers from the given n number, which is equal to C(n, K). If n = 4 and K = 2, then value of C(4, 2) = 4!/(2! * 2!) = 6.
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] ].
Explanation: The value of C(5, 3) = 5!/(2! * 3!) = 10.
Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
We use an idea similar to the subset sum problem to create possible combinations of K numbers from n numbers. For this, We select each number from 1 to n and recursively consider 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 consider both cases and recursively create all possible combinations. Note: The idea for 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 the 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 the temp array. Here, we also use a parameter index to exclude or include the current element in the combination and a parameter i to track the current element of the combination. Note: Our initial call is 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);
}
vector<vector<int>> findKCombination(int K, int n)
{
vector<vector<int>> output;
vector<int> temp(K, 0);
kCombination(output, temp, 0, n, 0, K);
return output;
}
public class Solution
{
private void kCombination(List<List<Integer>> output, List<Integer> temp,
int index, int n, int i, int K)
{
if (index == K)
{
output.add(new ArrayList<>(temp));
return;
}
if (i >= n)
return;
temp.set(index, i + 1);
kCombination(output, temp, index + 1, n, i + 1, K);
kCombination(output, temp, index, n, i + 1, K);
}
public static List<List<Integer>> findKCombination(int K, int n)
{
List<List<Integer>> output = new ArrayList<>();
List<Integer> temp = new ArrayList<>(K);
for (int i = 0; i < K; i = i + 1)
temp.add(0);
kCombination(output, temp, 0, n, 0, K);
return output;
}
}
def kCombination(output, temp, index, n, i, K):
if index == K:
output.append(temp.copy())
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)
def findKCombination(K, n):
output = []
temp = [0] * K
kCombination(output, temp, 0, n, 0, K)
return output
We call the recursive function kCombination with K and n as parameters, and in the worst case, it will get called twice in each step. This sequence of recursive calls will go till the base case index == K (when a combination of size K has been formed) or the value of i exceeds or equals n (this indicates that all elements have been considered).
So for every value of i, the number of recursive calls in each level of recursion is 2, and the depth of recursion is K. So, the total number of recursive calls = 2^0 + 2^1 + 2^2 + ... + 2^(K-1) = 2^K - 1 = O(2^K). In each recursive call, we perform constant-time operations.
If we consider all values of i from 1 to n, the overall time complexity = n *O(2^K) * O(1) = O(n * 2^K).
Here output array is part of the problem because we need to return all possible k combinations. So we should not consider output as a part of the space complexity.
We use a temp array of size K to store a single combination at a time during the recursive process. So the space complexity for the temp array = O(K).
Here recursion will also use a call stack that is proportional to the depth of recursion. In this case, the maximum depth of recursion is K. So the space complexity for the recursion call stack is O(K).
So overall space complexity = O(K) + O(K) = O(K).
The idea is to generate a combination tree where we fix each number from 1 to n and recursively build combinations of K numbers. Suppose we have n = 5 and K = 3.
To implement this:
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);
}
}
vector<vector<int>> findKCombination(int K, int n)
{
vector<vector<int>> output;
vector<int> temp(K, 0);
kCombination(output, temp, 0, 0, n, K);
return output;
}
public class Solution
{
public static List<List<Integer>> findKCombination(int K, int n)
{
List<List<Integer>> output = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
kCombination(output, temp, 0, 0, n, K);
return output;
}
private void kCombination(List<List<Integer>> output, List<Integer> temp,
int index, int start, int end, int K)
{
if (index == K)
{
output.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < end && end - i + 1 >= K - index; i = i + 1)
{
temp.add(i + 1);
kCombination(output, temp, index + 1, i + 1, end, K);
temp.remove(temp.size() - 1); // Remove the last element for backtracking
}
}
}
def findKCombination(K, n):
output = []
temp = [0] * K
kCombination(output, temp, 0, 0, n, K)
return output
def kCombination(output, temp, index, start, end, K):
if index == K:
output.append(temp[:]) # Make a copy of the current combination
return
for i in range(start, end):
if end - i + 1 >= K - index:
temp[index] = i + 1
kCombination(output, temp, index + 1, i + 1, end, K)
Here we are generating all combinations of size K that can be formed from n elements. So the total number of recursive calls will be approximately nCK (n choose K). So the time complexity of this code is O(nCK).
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!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.