AC backtracking dfs Python code (the problem needs clarification)


  • 0
    B
    class Solution(object):
        def combinationSum3(self, k, n):
            """
            :type k: int
            :type n: int
            :rtype: List[List[int]]
            """
            results = []
            
            if n < 6:
                return results
            
            def dfs_backtracking(results, temp, remaining):
                
                if remaining == 0 and len(temp) == k:
                    results.append(temp[:])
                if remaining < 0 or len(temp) > k:
                    return
                
                if not temp:
                    start = 1
                else:
                    start = temp[-1] + 1
                    
                for each in range(start, 10):
                    if each > remaining:
                        break
                    temp.append(each)
                    dfs_backtracking(results, temp, remaining - each)
                    temp.pop()
                
            dfs_backtracking(results, [], n)
            
            return results
    

    I think the problem is saying we need all distinct numbers in the solution


  • 0
    S

    I agree. The problem seems only requiring the solutions be unique, but not requiring the numbers used within each solution should be unique.


Log in to reply
 

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