Teaching Kids Programming – Backtracking Algorithm to List the Combination Sum (Recursive Depth First Search)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 is greater than 1, there are no valid combination.

Constraints:
2 <= k <= 9
1 <= n <= 60

Pure Combination Algorithm to Find Combination Sum

Given there are only 9 numbers to pick from, and we need to pick K numbers, so the combination number would be C(9, K) and this can be bruteforce. We can rely on Python’s itertools.combination to exhaust all possibility:

1

return [x for x in list(combinations(range(1, 10), k)) if sum(x)==n]

return [x for x in list(combinations(range(1, 10), k)) if sum(x)==n]

The problem is bounded by constant, and thus the time complexity is O(1), and the space complexity is O(1) since K is smaller or equal to 9.

We should directly return empty list when n is larger than 45 or K is larger than 9. This is due to that we can’t have duplicates in the chosen list.

If we were to implement the combination we can let it yield (bruteforcing all combination of size k, recursively):

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
 
        def comb(cur, i):
            if len(cur) == k:
                yield cur
                return
            for x in range(i, 10):
                yield from comb(cur + [x], x + 1)
        
        return [x for x in comb([], 1) if sum(x) == n]

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []

        def comb(cur, i):
            if len(cur) == k:
                yield cur
                return
            for x in range(i, 10):
                yield from comb(cur + [x], x + 1)
        
        return [x for x in comb([], 1) if sum(x) == n]

Backtracking Algorithm to Find the Combination Sum

A classic way is do backtracking algorithm which can be seen as a Depth First Search Algorithm with branch eliminations.

We backtrack when the current sum is larger than N or the number of numbers is larger than K. Be noted that the sum is required at each check which brings extra time complexity O(K).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
        
        def dfs(cur, a):
            curSum = sum(cur)
            if curSum > n or len(cur) > k:
                return
            if curSum == n and len(cur) == k:
                ans.append(cur[:])
                return            
            for i in range(a, 10):
                dfs(cur + [i], i + 1)    
 
        # start with a empty list and number 1                
        dfs([], 1)
        
        return ans

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
        
        def dfs(cur, a):
            curSum = sum(cur)
            if curSum > n or len(cur) > k:
                return
            if curSum == n and len(cur) == k:
                ans.append(cur[:])
                return            
            for i in range(a, 10):
                dfs(cur + [i], i + 1)    

        # start with a empty list and number 1                
        dfs([], 1)
        
        return ans

An improvement is: we can accumulate the sum in the recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
        
        def dfs(cur, curSum, a):
            if curSum > n or len(cur) > k:
                return
            if curSum == n and len(cur) == k:
                ans.append(cur[:])
                return            
            for i in range(a, 10):
                dfs(cur + [i], curSum + i, i + 1)        
 
        # start with a empty list (sum is zero) and number 1        
        dfs([], 0, 1)
        return ans

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
        
        def dfs(cur, curSum, a):
            if curSum > n or len(cur) > k:
                return
            if curSum == n and len(cur) == k:
                ans.append(cur[:])
                return            
            for i in range(a, 10):
                dfs(cur + [i], curSum + i, i + 1)        

        # start with a empty list (sum is zero) and number 1        
        dfs([], 0, 1)
        return ans

We can also use the Breadth First Search Algorithm to solve this problem: Teaching Kids Programming – Find Combination Sum via Breadth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —