Find all Possible Combinations of K Numbers from 1 to n

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.

Let’s understand the problem!

Given two numbers n and K and you have to find all possible combinations of K numbers from 1 to n.

Examples

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!

Discussed solution approaches

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

Solution approach 1: Inclusion and exclusion of every element

Solution idea

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

Solution Code C++

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;
}

Solution Code Java

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;
    }
}

Solution Code Python

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

Solution analysis

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

Solution approach 2: Fix elements and recur for creating a combination of K numbers

Solution idea

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[].

Solution code C++

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;
}

Solution code Java

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
        }
    }
}

Solution code Python

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)

Solution analysis

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

Critical ideas to think!

• 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?

Suggested coding problems to practice

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