**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!

- Inclusion and exclusion of every element
- Fix elements and recur for creating a combination of K numbers

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:

- The selected number is part of the solution or included in the set.
- The selected number is not part of the solution or not included in the set.

Suppose we have n = 4 and K = 2. The following tree diagram explains the generation of all combinations of size 2:

- We go left if we include the number and go right if we do not include the number.
- At each level, we include or exclude one number at a time.
- Each leaf node represents a combination 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:

- A 1-D array
**temp**to store any combination of K numbers. - The 2-D array
**output**stores all possible combinations of K numbers.

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.

- First, we fix the number 1 and recursively generate all unique combinations of size 3 starting with the number 1, such as {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, and {1, 4, 5}.
- Next, we fix the number 2 and recursively generate all unique combinations of size 3 starting with the number 2, such as {2, 3, 4}, {2, 3, 5}, and {2, 4, 5}.
- Then, we fix the number 3 and recursively generate all unique combinations of size 3 starting with the number 3, such as {3, 4, 5}.
- There would be no unique combinations of size 3 starting from 4 and 5.

To implement this:

- We use a temporary array temp[] to store all outputs one by one.
- We start from the first index in temp[] and fix elements at this index one by one, recursively moving to the remaining indexes.
- When the number of elements in temp[] becomes equal to K (the size of a combination), the recursion stops, and we print temp[].

```
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).

- What will be the space complexity?
- Why are we checking the condition (end - i + 1 ≥ K - ind) inside the loop
- Can we use this idea to solve other similar problems?
- Is there a different way to implement the above solution?
- What are the modifications in the algorithm in case of duplicate numbers?

- Combinations
- Combination Sum
- Permutations
- Combination Sum-2
- Next Permutation
- Print all subset
- Letter Combinations of a Phone Number
- Print all combinations of balanced parentheses

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.