LeetCode Number 416: Partition Equal Subset Sum

Question

Problem: MLE

I am confused as to why the LeetCode judge reports Memory Limit Exceeded when my solution looks close to the editorial solution. I not too familiar with @lru_cache and was using a memo dictionary at first that would take a tuple of index, and the sum of the subset. I change my code to see if that would make a difference, and it did not. With this being said, I am not just having a problem with memory, I am also having a problem with runtime. This is leading me to believe that there's a problem with the algorithm itself. Understanding why I am having these complications would be greatly appreciated as I am in the early stages of learning backtracking + memo / dynamic programing.

Mentions -> The find method is the one I created, while dfs is the LeetCode editorial for top-down approach. Also, feel free to comment on the structure or any opinions.

Link: https://leetcode.com/problems/partition-equal-subset-sum/?envType=daily-question&envId=2025-04-07

Problem Statement:

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

 class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        equal = sum(nums)
        if equal & 1 == 1:
            return False
        equal //= 2

        @lru_cache(maxsize=None)
        def find(place, sum_):
            if place >= len(nums) or sum_ > equal :
                return False
            if sum_ == equal:
                return True       
            temp1 = find(place+1,sum_ + nums[place])          
            temp2 = find(place+1,sum_)
            return temp1 | temp2
        return find(0,0)

---

Leetcode Implementation Below

        @lru_cache(maxsize=None)
        def dfs(nums: Tuple[int], n: int, subset_sum: int) -> bool:
            # Base cases
            if subset_sum == 0:
                return True
            if n == 0 or subset_sum < 0:
                return False
            result = (dfs(nums, n - 1, subset_sum - nums[n - 1])
                    or dfs(nums, n - 1, subset_sum))
            return result

        # find sum of array elements
        total_sum = sum(nums)

        # if total_sum is odd, it cannot be partitioned into equal sum subsets
        if total_sum % 2 != 0:
            return False

        subset_sum = total_sum // 2
        n = len(nums)
        return dfs(tuple(nums), n - 1, subset_sum)  

Answer 1

Performance

Since your primary concern is mem/runtime, let's address this first. Your algorithm appears correct, but is missing one small optimization: laziness. You always traverse both branches to or them later, while the optimal code should abort early if the left branch already produces True.

Fortunately, or (but not bit-or | that you're using - please just don't) short-circuits in python. So the following (removing temp1 and temp2 and inlining the calls with or) should be enough to get it accepted, I guess:

from functools import lru_cache

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        equal = sum(nums)
        if equal & 1 == 1:
            return False
        equal //= 2

        @lru_cache(maxsize=None)
        def find(place, sum_):
            if place >= len(nums) or sum_ > equal :
                return False
            if sum_ == equal:
                return True       
            return (
                find(place+1,sum_ + nums[place])
                or find(place+1,sum_)
            )
        return find(0,0)

Other notes

• Don't abuse bitwise operations (% 2 is much less cryptic than & 1, even though both will be understood by any python dev). If you're coming from other languages, || is equivalent to python's or, && - and, and |/&/~/^ are the same bitwise operators.
• Good job with sum_ variable! Appended underscore is a good way to deal with std name collisions.
• Try to find some better ident name than equal- what exactly is equal here?..
• Don't learn patterns from leetcode, they use awkward conventions that work in most languages (this shouldn't be a class, names should be snake_case and not camelCase, typing.List is deprecated since python 3.8 and so isn't necessary in any non-EOL python, implicit "prelude" imports are worse than failure, ...)
• As already mentioned, please run black of ruff on your code. Put whitespace around operators and after commas separating function arguments. Don't put spaces before colons introducing blocks (if something :).
• Use type hints consistently - either do or don't. Your outer method is annotated, while find is not. If you just inherited hints from Leetcode, you can safely remove them - type hints are not mandatory.

Answer 2

The following only applies to your code (with the find method), not the dfs LeetCode example.

I can not think of a way to address the performance issues, but here are some minor code style suggestions. As you mentioned, you likely need a different algorithm.

Layout

Move the helper function to the top after the canPartition line. Having it in the middle of the code interrupts the natural flow of the code (from a human readability standpoint).

Documentation

It is great that you used type hints for the main function.

The PEP 8 style guide recommends adding docstrings for functions. I realize the code is submitted to the LeetCode site as a programming challenge, but for general code review, it would be good to add a docstring summarizing the purpose of the functions. Add a description of your algorithm.

Mentioning that find is recursive would be helpful, as would type hints for this function.

Naming

PEP 8 recommends snake_case for function names:

canPartition would be can_partition.

Tools

The black program can be used to automatically reformat your code for consistent whitespace around operators.