416. Partition Equal Subset Sum - Explanation

Problem Link

Description

You are given an array of positive integers nums.

Return true if you can partition the array into two subsets, subset1 and subset2 where sum(subset1) == sum(subset2). Otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]

Output: true

Explanation: The array can be partitioned as [1, 4] and [2, 3].

Example 2:

Input: nums = [1,2,3,4,5]

Output: false

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 50

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n * t) time and O(n * t) space, where n is the size of the input array and t is half the sum of the array elements.

Hint 1

If the sum of the array elements is not even, we can immediately return false. Think in terms of recursion, where we try to build a subset with a sum equal to half of the total sum. If we find such a subset, the remaining elements will automatically form another subset with the same sum. The entire array can also be considered as one subset, with the other being empty. Can you visualize this as a decision tree to process the array recursively?

Hint 2

We recursively iterate through the array with index i. At each step, we decide whether to include the current element in the subset or not. Instead of forming the subset explicitly, can you think of a better approach? Maybe you only need to track the subset sum rather than generating the subset itself.

Hint 3

We can track the subset sum using a variable curSum. At each step, we make two recursive calls. If adding the current element does not exceed the target, we include it. If either path leads to a solution, we immediately return true. Can you determine the base case for this recursion? All elements in the array are positive.

Hint 4

If curSum equals half the sum of the array elements, we return true. If index i goes out of bounds, we return false. This solution is exponential, but we can use memoization to cache recursive call results and avoid redundant computations. We can use a hash map or a 2D array with dimensions n * t, where n is the size of the input array and t is half the sum of the input array elements.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

The problem asks whether we can split the array into two subsets with equal sum.

Key observation:

• If the total sum is odd, it’s impossible → return False.
• Otherwise, the problem becomes:

  Can we pick a subset whose sum is totalSum / 2?

This is a classic subset sum decision problem.

Using recursion:

• At each index, we have two choices:
  1. Take the current number into the subset
  2. Skip the current number
• We keep reducing the target (sum/2) until:
  • Target becomes 0 → success
  • We run out of numbers or target becomes negative → failure

Algorithm

1. Compute totalSum = sum(nums)
2. If totalSum is odd, return False
3. Set target = totalSum // 2
4. Define dfs(i, target):
   • If target == 0, return True
   • If i == len(nums) or target < 0, return False
   • Try both choices:
     • Skip nums[i]
     • Take nums[i] (reduce target)
5. Return dfs(0, target)

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

        def dfs(i, target):
            if i >= len(nums):
                return target == 0
            if target < 0:
                return False

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

        return dfs(0, sum(nums) // 2)

Time & Space Complexity

• Time complexity: $O(2 ^ n)$
• Space complexity: $O(n)$

---

2. Dynamic Programming (Top-Down)

Intuition

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

Key observations:

• 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.

In plain recursion, many subproblems repeat:

• Same index i
• Same remaining target

To avoid recomputing them, we store results in a DP table:

• memo[i][t] = whether it’s possible to form sum t using elements from index i onward.

This turns the exponential recursion into a polynomial-time solution.

Algorithm

1. Compute total = sum(nums)
2. If total is odd, return False
3. Set target = total // 2
4. Create a memo table memo[n][target + 1] initialized to -1
5. Define dfs(i, target):
   • If target == 0, return True
   • If i == n or target < 0, return False
   • If result already exists in memo, return it
   • Otherwise:
     • Option 1: skip current element → dfs(i + 1, target)
     • Option 2: take current element → dfs(i + 1, target - nums[i])
     • Store and return the OR of both choices
6. Return dfs(0, target)

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)

Time & Space Complexity

• Time complexity: $O(n * target)$
• Space complexity: $O(n * target)$

Where $n$ is the length of the array $nums$ and $target$ is the sum of array elements divided by 2.

---

3. Dynamic Programming (Bottom-Up)

Intuition

This is a classic 0/1 subset sum DP.

We want to split nums into two subsets with equal sum. That’s only possible if:

• total = sum(nums) is even
• there exists a subset that sums to target = total / 2

Instead of trying all subsets (exponential), we build the answer gradually:

• Let dp[i][j] mean: using the first i numbers, can we form sum j?

For each number, we have two choices:

• Skip it → the possibility stays dp[i-1][j]
• Take it (only if nums[i-1] <= j) → check dp[i-1][j - nums[i-1]]

If either is true, then dp[i][j] is true.

Algorithm

1. Compute total = sum(nums). If total is odd, return False.
2. Set target = total // 2, n = len(nums).
3. Create a DP table dp of size (n+1) x (target+1) filled with False.
4. Base case: dp[i][0] = True for all i (sum 0 is always achievable by taking nothing).
5. Fill DP:
   • For i from 1..n:
     • For j from 1..target:
       • 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]
6. Return dp[n][target].

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]

Time & Space Complexity

• Time complexity: $O(n * target)$
• Space complexity: $O(n * target)$

Where $n$ is the length of the array $nums$ and $target$ is the sum of array elements divided by 2.

---

4. Dynamic Programming (Space Optimized)

Intuition

This is the same subset sum idea as before, but optimized to use 1D DP.

Instead of keeping a full 2D table (dp[i][j]), we only track:

• dp[j] → whether sum j is achievable using numbers processed so far

At each number, we build a new state (nextDp) from the previous one:

• Either we don’t take the current number → dp[j]
• Or we take it (if possible) → dp[j - nums[i]]

This works because each state only depends on the previous row.

Algorithm

1. Compute total = sum(nums). If total is odd, return False.
2. Set target = total // 2.
3. Initialize a boolean array dp of size target + 1.
   • dp[0] = True (sum 0 is always possible).
4. 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.
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)
        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]

Time & Space Complexity

• Time complexity: $O(n * target)$
• Space complexity: $O(target)$

Where $n$ is the length of the array $nums$ and $target$ is the sum of array elements divided by 2.

---

5. Dynamic Programming (Hash Set)

Intuition

This approach also solves Partition Equal Subset Sum, but instead of arrays, it uses a Hash Set to track all achievable sums.

At any point:

• dp contains all subset sums that can be formed using the processed numbers.

For each new number:

• Every existing sum t can either:
  • Stay the same (don’t pick the number)
  • 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.
2. Set target = total // 2.
3. Initialize a set dp = {0} (sum 0 is always possible).
4. 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.
5. 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

Time & Space Complexity

• Time complexity: $O(n * target)$
• Space complexity: $O(target)$

Where $n$ is the length of the array $nums$ and $target$ is the sum of array elements divided by 2.

---

6. Dynamic Programming (Optimal)

Intuition

This is the most optimal DP solution for Partition Equal Subset Sum.

We reduce the problem to:

Can we pick some numbers whose sum equals target = total_sum / 2?

We use a 1D DP array where:

• dp[j] = True means we can form sum j using some of the numbers so far.

Key idea:

• For each number, update the DP from right to left so that each number is used only once.
• This avoids overwriting results from the same iteration.

Algorithm

1. Compute total = sum(nums). If total is odd, return False.
2. Set target = total // 2.
3. Create a boolean array dp of size target + 1.
   • 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]

Time & Space Complexity

• Time complexity: $O(n * target)$
• Space complexity: $O(target)$

Where $n$ is the length of the array $nums$ and $target$ is the sum of array elements divided by 2.

---

7. Dynamic Programming (Bitset)

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

        target = total // 2
        dp = 1 << 0

        for num in nums:
            dp |= dp << num

        return (dp & (1 << target)) != 0

Time & Space Complexity

• Time complexity: $O(n * target)$
• Space complexity: $O(target)$

Where $n$ is the length of the array $nums$ and $target$ is the sum of array elements divided by 2.