Bug Report for partition-equal-subset-sum

[austinthiel]

Bug Report for https://neetcode.io/problems/partition-equal-subset-sum

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

A greedy approach to this problem results in a passing solution, but the greedy approach is flawed:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False
        
        nums.sort(reverse=True)
        
        goal = sum(nums) // 2
        curr = 0
        for n in nums:
            if curr + n <= goal:
                curr += n
            if curr == goal:
                return True
        return False

From Claude:

This greedy approach doesn't actually solve canPartition correctly. "Take the largest item that still fits under goal" can wedge you into a dead end.
Counterexample: nums = [5, 4, 3, 3, 3, 2], sum = 20, goal = 10.
Greedy trace (descending): takes 5 (curr=5), takes 4 (curr=9), then nothing else fits under 10 → returns False. But {5, 3, 2} = 10 and {4, 3, 3} = 10, so the answer should be True.
The reason greedy fails is that subset-sum has no greedy-choice property — committing to the 4 early blocks the valid combination that needed two 3s and a 2 instead. The standard correct solution is the subset-sum DP