Combination Sum III

Patrick Leaton
Published: May 13, 2021, 4:09 a.m.
Problem Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.

Example 4:

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

Example 5:

Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
There are no other valid combinations.

 

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 60

 

The description was taken from https://leetcode.com/problems/combination-sum-iii/.

Problem Solution

#O(9!*K/(9-K)!) Time, O(K) Space
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        output = []
        def backtrack(start:int, combo:list, remaining:int) -> None:
            if remaining == 0 and len(combo) == k:
                output.append(list(combo))
                return
            elif remaining < 0 or len(combo) == k:
                return
            for i in range(start, 10):
                if i > remaining:
                    return
                combo.append(i)
                backtrack(i+1, combo, remaining-i)
                combo.pop()
        backtrack(1, [], n)
        return output
 
           

Problem Explanation

The only difference between this solution and Combination Sum II is we'll now need to check whether a valid solution is also size k, that's it.

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, a combo list that contains a Depth First Search path's current combination, as well as a remaining value that indicates what needs to be added to this current combination for it to equal the target value.

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

 

Let's set a couple of base cases for this function.

First, if the remaining value equals zero and the length of the combo equals k, then that means that the candidates within the current combination sum to the target value and are of the target length.  If that is the case, then we will append the combination to the output by taking a deep copy so that the list isn't overwritten later.

We will then return from the function.

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

 

Also, if the remaining value is less than zero or the length of the combo equals k, then that means we overshot the target, or we have undershot the target but are about to exceed the target length.

We should return from this DFS path here since it will not lead to any combination that we will be able to use.

            elif remaining < 0 or len(combo) == k:
                return

 

Note: the inclusion of checking the length within the base cases is basically the only difference between this question and the previous two.

We will now start creating the backtracking logic.

Let's create a loop that will iterate from a given starting number to ten since we are only using values between one and nine since python excludes the last value within a given range.

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

            for i in range(start, 10):

 

Next, we will implement the optimization that we can implement because our range is sorted.

If the number in our current iteration is greater than the remaining value, then we should return now because this current DFS path is bad and we will overshoot our target by adding any more values from the range.

This step isn't required but helps tremendously to prune the recursion tree.

                if i > remaining:
                    return

 

Next, we will append the current candidate number from the current iterator to the current combo and recurse the function by incrementing the starting number to the current iterator plus one, since we can't reuse candidate values within a combo unlike the first version of this question.  We will also be passing the combo and subtracting the remaining value by the current candidate.

                combo.append(i)
                backtrack(i+1, combo, remaining-i)

 

After we have shot our DFS yoyo down and it has returned back to us, we will pop the last candidate from our combo.  

                combo.pop()

 

The reason we do this is that we want to allow the function to circulate increasing numbers for each position from the pool of candidates until we have gathered each combination from each valid 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, an initial empty combination, and the target number, n as the remaining value.

        backtrack(1, [], n)

 

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

        return output

The time complexity is bound by the target length value.  For each combination of the target length, the combination would be nine factorial, since we are only using values between one and nine without duplicates and would decrease for each additional value.  

The space complexity required is also determined by the target length value.