Partition Equal Subset Sum

We want to split nums into two subsets with equal sum. That's only possible if total is even. Then our goal reduces to a classic subset sum problem: can we form exactly target = total / 2 using our available elements?

Intuition: This is the same subset sum idea as the recursive approach, but optimized using memoization.

• If the total sum is odd, we can’t split it into two equal subsets.
• Otherwise, we only need to check if some subset sums to totalSum / 2.
• To avoid recomputing subproblems matching the same index i and remaining target, we store results in a DP table: memo[i][t].

Algorithm:

1. Compute total = sum(nums). If total is odd, return false. Set target = total // 2.
2. Create a memo table initialized to -1.
3. Define dfs(i, target):
   • If target == 0, return true.
   • If i == n or target < 0, return false.
   • If result exists in memo, return it.
   • Else: Result is dfs(i + 1, target) OR dfs(i + 1, target - nums[i])
4. Store and return the OR of both choices.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0: return False

        target = total // 2
        n = len(nums)
        memo = [[-1] * (target + 1) for _ in range(n + 1)]

        def dfs(i, target):
            if target == 0: return True
            if i >= n or target < 0: return False
            if memo[i][target] != -1: return memo[i][target]

            memo[i][target] = (dfs(i + 1, target) or dfs(i + 1, target - nums[i]))
            return memo[i][target]

        return dfs(0, target)

Intuition: This is a classic 0/1 subset sum DP.

Let dp[i][j] mean: using the first i numbers, can we form sum j? For each number, we have two choices: Skip it (possibility stays dp[i-1][j]) or Take it (check dp[i-1][j - nums[i-1]]).

Algorithm:

1. Compute total = sum(nums). Base failure if odd. Set target = total // 2.
2. Create a DP table dp of size (n+1) x (target+1) filled with false.
3. Base case: dp[i][0] = true for all i.
4. Fill DP matrix matching nums logic recursively iteratively left to right.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0: return False

        target = total // 2
        n = len(nums)
        dp = [[False] * (target + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = True

        for i in range(1, n + 1):
            for j in range(1, target + 1):
                if nums[i - 1] <= j:
                    dp[i][j] = (dp[i - 1][j] or dp[i - 1][j - nums[i - 1]])
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[n][target]

Intuition: Instead of keeping a full 2D table, we only track the latest row dp[j] indicating whether sum j is achievable processed so far. At each number, we build a new state nextDp from the previous one. Either we don't take it (dp[j]) or we take it (dp[j - num]).

Algorithm:

1. Compute total = sum(nums). If total is odd, return false. Set target = total // 2.
2. Initialize a boolean array dp of size target + 1. dp[0] = true (sum 0 is always possible).
3. For each number num in nums:
   • Create a new array nextDp.
   • For each sum j from 1 to target:
   • If j >= num: nextDp[j] = dp[j] OR dp[j - num]
   • Else: nextDp[j] = dp[j]
   • Replace dp with nextDp.
4. Return dp[target].

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2: return False

        target = sum(nums) // 2
        dp = [False] * (target + 1)
        nextDp = [False] * (target + 1)

        dp[0] = True
        for i in range(len(nums)):
            for j in range(1, target + 1):
                if j >= nums[i]:
                    nextDp[j] = dp[j] or dp[j - nums[i]]
                else:
                    nextDp[j] = dp[j]
            dp, nextDp = nextDp, dp

        return dp[target]

Intuition: Instead of arrays, it uses a Hash Set to track all achievable sums. Every existing sum t can either stay the same (don’t pick the number) or become t + num (pick the number). If at any time we form target, we can stop early and return True.

Algorithm:

1. Compute total = sum(nums). If total is odd, return false. Set target = total // 2.
2. Initialize a set dp = {0} (sum 0 is always possible).
3. Traverse numbers (order doesn't matter):
   • Create an empty set nextDP.
   • For each sum t in dp:
   • If t + num == target, return true.
   • Add t to nextDP (skip current number).
   • Add t + num to nextDP (take current number).
   • Replace dp with nextDP.
4. If loop finishes without finding target, return false.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2: return False

        dp = set()
        dp.add(0)
        target = sum(nums) // 2

        for i in range(len(nums) - 1, -1, -1):
            nextDP = set()
            for t in dp:
                if (t + nums[i]) == target:
                    return True
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP
        return False

Intuition: This is the most optimal DP solution for Partition Equal Subset Sum. We reduce the problem using a 1D DP array but instead of a secondary swap array, we traverse backwards from target down to num to avoid overwriting results from the same iterative loop constraint!

Algorithm:

1. Compute total = sum(nums). If total is odd, return false. Set target = total // 2.
2. Create a boolean array dp of size target + 1.
3. Initialize dp[0] = true (sum 0 is always achievable).
4. For each number num in nums:
   • Traverse j from target down to num:
   • Set dp[j] = dp[j] OR dp[j - num]
5. Return dp[target].

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        if sum(nums) % 2: return False

        target = sum(nums) // 2
        dp = [False] * (target + 1)

        dp[0] = True
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]