Implement nested backtracking function with memoization - Python3

Question

I am new to programming and currently practicing the Leetcode questions. I am solving one of the questions using backtracking with memoization. The algorithm is not hard to understand, my code looks like this:

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        def recursiveWithMem(S, i) -> int:
            if i == len(nums):
                return (1 if S == 0 else 0)

            key = (i, S)
            if key in mem:
                return mem[key]

            r = recursiveWithMem(S - nums[i], i + 1) + recursiveWithMem(S + nums[i], i + 1)
            mem[key] = r
            return r
        
        mem = {}
        return recursiveWithMem(S, 0)

When I look at other people's submissions they pass the mem as an attribute of the function. It doesn't affect the time complicity, but the second method uses 15MB memory and I implementation uses 35MB.


def findTargetSumWays(self, nums: List[int], S: int) -> int:
        def recursiveWithMem(S, i, mem) -> int:
            if i == len(nums):
                return (1 if S == 0 else 0)

            key = (i, S)
            if key in mem:
                return mem[key]

            r = recursiveWithMem(S - nums[i], i + 1, mem) + recursiveWithMem(S + nums[i], i + 1, mem)
            mem[key] = r
            return r
        
        mem = {}
        return recursiveWithMem(S, 0, mem)

I also tried @cache, it uses 45MB of memory. I am very confused why passing memo into the function can help reduce memory use. Please help! Thank you in advance!

KnightKnight · Accepted Answer · 2021-03-25 06:13:21Z

1

See what is happening is that the declaration of mem you have done is below the function declaration so the mem you are using inside the function has nothing to do with the mem you have declared below the declaration of that function it is not scoped to it instead each time a new Dictionary is being created with each function call , where as the codes you are seeing with 15 mb ,which have passed mem as an arguement ensures that no new copies of Mem dictionary are created for each function call . I hope this makes things clearer.

answered Mar 25, 2021 at 6:13

KnightKnight

2172 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lzimng Over a year ago

I tried to move the declaration of mem before the function, it still uses 35MB. Also notice that nums is not passed as a parameter to the nested function, but the nested function is still able to use it.

Collectives™ on Stack Overflow

Implement nested backtracking function with memoization - Python3

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related