A recursive Python version


  • 0
    Q
    class Solution:
        def combinationSum3(self, k, n):
            def helper(target, number, times, resultList):
                if times > k: return
                resultList.append(number)
                nextNumber = target - number
                if nextNumber == 0 and times == k: results.append(resultList)
                else:
                    for num in range(number+1,10):
                            helper(nextNumber, num, times + 1, resultList + [])
            results = []
            for num in range(1,10):
                helper(n,num,1,[])
            return results

  • 0
    C

    If I replace "resultList + []" with "resultList", the result is incorrect. Could you please explain it in detail? Thanks.


  • 0
    Q

    Yes, it is easy to understand.
    During every recursion, you need a new list to save the result.
    For example, supposing the target is 17 and current number is 2 and current resultList is [1,2]
    so next we will go into the recursion of 3. If you just use the same resultList, 3 will be appended to the list. So when this recursion ends, and return to the recursion of 2, the resultList has been changed permanently and it will go into the recursion of 4 with wrong resultList. This si the reason why we should use a new list every time.


  • 0
    Q
    This post is deleted!

Log in to reply
 

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