Teaching Kids Programming – Find Combination Sum via Breadth First Search Algorithm

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

Yesterday we talked about the classic Backtracking Algorithm (Recursive Depth First Search) to find the combination sum: Teaching Kids Programming – Backtracking Algorithm to List the Combination Sum (Recursive Depth First Search)

Find Combination Sum via Breadth First Search Algorithm

We can perform the Breadth First Search algorithm to find out the combination sum. Each node in the tree represents a choice of numbers, and we can traversal the tree via BFS via a Queue Data Structure – First In First Out. We only push the children nodes if the pick is less than K numbers and the sum is less than N.

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

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
        q = deque([([], 0, 1)])
        while q:
            nn = len(q)
            for _ in range(nn):
                cur, curSum, x = q.popleft()
                if curSum < n and len(cur) < k:
                    for i in range(x, 10):
                        q.append((cur + [i], curSum + i, i + 1))
                elif curSum == n and len(cur) == k:
                    ans.append(cur)
        return ans

class Solution:
    def combinationSum(self, k: int, n: int) -> List[List[int]]:
        ans = []
        if n > 45 or k > 9:
            return []
        q = deque([([], 0, 1)])
        while q:
            nn = len(q)
            for _ in range(nn):
                cur, curSum, x = q.popleft()
                if curSum < n and len(cur) < k:
                    for i in range(x, 10):
                        q.append((cur + [i], curSum + i, i + 1))
                elif curSum == n and len(cur) == k:
                    ans.append(cur)
        return ans

–EOF (The Ultimate Computing & Technology Blog) —