Combinations

Patrick Leaton
Published: May 5, 2021, 8:15 p.m.
Problem Description

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

You may return the answer in any order.

 

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

 

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= n

 

The description was taken from https://leetcode.com/problems/combinations/.

Problem Solution

#O(K*N!/(N-k)!k!) Time, O(N!/(N-k)!k!) Space
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        output = []
        def backtrack(start:int, combo:list) -> None:
            if len(combo) == k:
                output.append(list(combo))
                return
            for i in range(start, n+1):
                combo.append(i)
                backtrack(i+1, combo)
                combo.pop()
        backtrack(1, [])
        return output

Problem Explanation

If we are given a problem that requires us to generate each possible combination of something, that is typically an indication that backtracking can be applied.

Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function.  This allows us to circulate elements into each valid position so that we can generate each valid combination. 

A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement.  Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.  

This is what allows us to generate each combination, adding and removing a parenthesis for each position where it'd be valid.

Let's start by initializing our output array.

        output = []

Next, we will create our recursive, backtrack function. 

The function will take an index to begin a traversal from and a combo list that contains a Depth First Search path's current combination.

        def backtrack(start:int, combo:list) -> None:

 

The base case we will want to check at the beginning of each function call is if the length of the combo has reached K.

If it has, we will append the combo to the output and end this recursive path.  We will need to take a deep copy of the combo since it will be edited later and we don't want it to be overwritten.

            if len(combo) == k:
                output.append(list(combo))
                return

 

We will now start creating the backtracking logic.

Let's create a loop that will iterate from a given starting number to the last number, n.

This is how we will split up the scope of each combination through recursion.  

            for i in range(start, n+1):

 

Next, we will append the current iterator from our loop to our combo, then recurse the function while also incrementing the current iterator number and passing our current combo.  After we have returned from a deeper function call, we will backtrack by revering our change.

                combo.append(i)
                backtrack(i+1, combo)
                combo.pop()
 

The reason we pop the last number off of the combo to do this is we want to allow the function to circulate numbers for each position from one to n until we have gathered each combination from each DFS path.

Now that we have our backtrack function built, we just need to make the initial call by passing one as the starting number and an empty combination to the function.

        backtrack(1, [])

 

Once we have our output that contains each combination, we will return it and we're done with this question.

        return output

As for the time and space complexities, it takes N!/(N-k)!k! time to build and store every combination, and we have to do that k times.

This illustration shows what the flow of the DFS and backtracking would look like when n equals four and k equals two.

image