Share my Python solution with Iterative Backtracking


  • 2
    Y
    class Solution:
    # @param {integer} k
    # @param {integer} n
    # @return {integer[][]}
    def combinationSum3(self, k, n):
        # Iterative backtracking: AC in 60 ms
        # -----------------------------------
        #
        ans = []
        stack = [(0, 1, [])]  # (total, start, combination)
        while stack:
            total, start, comb = stack.pop()
            if total == n and len(comb) == k:
                ans.append(comb)
                continue
    
            for i in range(start, 10):
                tmp_total = total + i
                if tmp_total > n:
                    break
                stack.append((tmp_total, i + 1, comb + [i]))
        return ans

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.