216. Combination Sum III

Problem Statement

link: https://leetcode.com/problems/combination-sum-iii/ https://leetcode.cn/problems/combination-sum-iii/

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:

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

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

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

Solution Approach

The solution employs a backtracking algorithm to find valid combinations of k numbers that sum up to n within the constraints of using numbers from 1 to 9 and each number at most once.

Algorithm

1. Define a recursive backtracking function that considers three parameters: the current number, k (remaining count of numbers to select), and n (remaining sum).
2. Within the backtracking function, check if k has reached 0. If so, check if n is also 0. If both conditions are met, add the current combination to the result list.
3. Recursively iterate through numbers from the current number (1 to 9), updating k, n, and the combination while backtracking and exploring all possible valid combinations.

Implement

    class Solution:
      def combinationSum3(self, k: int, n: int) -> List[List[int]]:
          def backtracking(cur, k, n, tmp):
              if k == 0:
                  if n == 0:
                      res.append(tmp[:])
                  return
              for i in range(cur,10):
                  if i > n:
                      return
                  tmp.append(i)
                  backtracking(i + 1, k - 1, n - i,tmp)
                  tmp.pop()
          
          res = []
          backtracking(1, k, n, [])
          return res

 

    
    

Twitter  facebook  Email