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.

Examples

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints

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

Thinking Process

This problem is a classic variation of the 0/1 Knapsack Problem.

  1. Total Sum Check: First, calculate the sum of all elements. If the total sum is odd, it’s impossible to split it into two equal integer partitions, so return false.
  2. Target Sum: If the total sum is even, our goal is to find a subset of elements that sums up to target = totalSum / 2. If we find such a subset, the remaining elements will automatically sum to target as well.
  3. Transformation: The problem becomes: “Can we pick a subset of items from nums such that their sum is exactly target?”

1. Brute Force (DFS)

We can try to include or exclude each element recursively.

  • Base Case: If target == 0, we found a subset. If target < 0 or we run out of elements, return false.
  • Recursive Step: For index i, we can either:
    • Include nums[i] in the sum (subtract from target).
    • Exclude nums[i] (keep target same).

Time Complexity: O(2^n) - TLE.

2. Top-Down DP (Memoization)

The brute force approach re-calculates the same state (index, currentTarget) multiple times. We can cache these results. Note: Using vector<vector<int>> (with -1 for unvisited) is preferred over vector<vector<bool>> to distinguish between “visited and false” vs “unvisited”.

Time Complexity: O(n · text{target}) Space Complexity: O(n · text{target})

3. Bottom-Up DP (2D)

We can build a table dp[i][j] representing whether sum j is possible using the first i items.

  • dp[i][j] = dp[i-1][j] (don’t include item i) || dp[i-1][j - nums[i-1]] (include item i).

4. Space Optimized DP (1D)

Notice that dp[i][j] only depends on the previous row dp[i-1]. We can reduce the space to a 1D array. When iterating through the 1D array, we must iterate backwards from target to nums[i]. This ensures that when we calculate dp[j], we are using values from the previous iteration (effectively dp[i-1]), not values we just updated in the current iteration.

Time Complexity: O(n · text{target}) Space Complexity: O(text{target})

1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

Approach 1: DFS (Time Limit Exceeded)

class Solution:
    def canPartition(self, nums):
        totalSum = sum(nums)
        
        if totalSum % 2 != 0:
            return False
        
        target = totalSum // 2
        
        return self.dfs(nums, len(nums) - 1, target)
    
    def dfs(self, nums, n, target):
        if target == 0:
            return True
        if n < 0 or target < 0:
            return False
        
        # take or not take
        return (
            self.dfs(nums, n - 1, target - nums[n]) or
            self.dfs(nums, n - 1, target)
        )

Solution Explanation

Approach: 1D DP (this problem)

Key idea: This problem is a classic variation of the 0/1 Knapsack Problem.

How the code works:

  1. Total Sum Check: First, calculate the sum of all elements. If the total sum is odd, it’s impossible to split it into two equal integer partitions, so return false.
  2. Target Sum: If the total sum is even, our goal is to find a subset of elements that sums up to target = totalSum / 2. If we find such a subset, the remaining elements will automatically sum to target as well.
  3. Transformation: The problem becomes: “Can we pick a subset of items from nums such that their sum is exactly target?”
    • Base Case: If target == 0, we found a subset. If target < 0 or we run out of elements, return false.
    • Recursive Step: For index i, we can either:
    • Include nums[i] in the sum (subtract from target).

Walkthrough — input nums = [1,5,11,5], expected output true:

The array can be partitioned as [1, 5, 5] and [11].

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Pattern: 1D DP (this problem)
  • Base Case: If target == 0, we found a subset. If target < 0 or we run out of elements, return false.
  • Recursive Step: For index i, we can either:

References

Template Reference