Combinations

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 as 2>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 length k 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 range start to n , append i in the current combination sequence and look for the rest of the elements that needed to be filled in the curr_comb . If all possible combinations have been explored, then pop out that i and explore the rest possible sequences
• Whenever the curr_comb sequence becomes the length of k , append it to the final combs 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!