101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming (2D) - Complex approach
  2. Dynamic Programming (1D) - Complex approach

Approach 1: Dynamic Programming (2D)

The key insight for solving this problem is to recognize that it's equivalent to finding a subset of the array with a sum equal to half of the total sum.

First, we calculate the total sum of the array. If the total sum is odd, it's impossible to partition the array into two equal subsets, so we return false.

If the total sum is even, we need to find a subset with a sum equal to totalSum / 2. This is a classic 0/1 Knapsack problem, which can be solved using dynamic programming.

Let's define a 2D DP array dp[i][j] where dp[i][j] represents whether it's possible to form a sum j using the first i elements of the array.

The base cases are:

  • dp[0][0] = true (it's always possible to form a sum of 0 with 0 elements)
  • dp[0][j] = false for all j > 0 (it's impossible to form a positive sum with 0 elements)

For each element nums[i-1] and each possible sum j, we have two options:

  1. Exclude the current element: dp[i][j] = dp[i-1][j]
  2. Include the current element (if j >= nums[i-1]): dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]

The final answer is dp[n][target], where n is the number of elements in the array and target = totalSum / 2.

Algorithm:

  1. Calculate the total sum of the array.
  2. If the total sum is odd, return false.
  3. Set target = totalSum / 2.
  4. Initialize a 2D DP array dp of size (n+1) x (target+1), where dp[i][j] represents whether it's possible to form a sum j using the first i elements.
  5. Set dp[0][0] = true and dp[0][j] = false for all j > 0.
  6. For each element nums[i-1] and each possible sum j:
  7. a. Exclude the current element: dp[i][j] = dp[i-1][j]
  8. b. Include the current element (if j >= nums[i-1]): dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]]
  9. Return dp[n][target].

Time Complexity:

O(n * target)

Where n is the number of elements in the array and target is half of the total sum. We need to fill a 2D DP array of size (n+1) x (target+1).

Space Complexity:

O(n * target)

We use a 2D DP array of size (n+1) x (target+1).

Approach 2: Dynamic Programming (1D)

We can optimize the space complexity of the previous approach by using a 1D DP array instead of a 2D DP array.

Let's define a 1D DP array dp[j] where dp[j] represents whether it's possible to form a sum j using the elements of the array.

The base case is dp[0] = true (it's always possible to form a sum of 0).

For each element nums[i] and each possible sum j from target down to nums[i], we update dp[j] as follows:

dp[j] = dp[j] || dp[j-nums[i]]

We iterate through the sums in reverse order to avoid using the updated values in the same iteration.

The final answer is dp[target], where target = totalSum / 2.

Algorithm:

  1. Calculate the total sum of the array.
  2. If the total sum is odd, return false.
  3. Set target = totalSum / 2.
  4. Initialize a 1D DP array dp of size (target+1), where dp[j] represents whether it's possible to form a sum j.
  5. Set dp[0] = true and dp[j] = false for all j > 0.
  6. For each element nums[i]:
  7. a. For each possible sum j from target down to nums[i]:
  8. i. dp[j] = dp[j] || dp[j-nums[i]]
  9. Return dp[target].

Time Complexity:

O(n * target)

Where n is the number of elements in the array and target is half of the total sum. We need to iterate through each element and each possible sum.

Space Complexity:

O(target)

We use a 1D DP array of size (target+1).

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function canPartition(nums):
    totalSum = sum of all elements in nums
 
    // If the total sum is odd, return false
    if totalSum % 2 != 0:
        return false
 
    target = totalSum / 2
    n = length of nums
 
    // Initialize DP array
    dp = new 2D array of size (n+1) x (target+1)
 
    // Base cases
    dp[0][0] = true
    for j from 1 to target:
        dp[0][j] = false
 
    // Fill DP array
    for i from 1 to n:
        for j from 0 to target:
            // Exclude the current element
            dp[i][j] = dp[i-1][j]
 
            // Include the current element if possible
            if j >= nums[i-1]:
                dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]]
 
    return dp[n][target]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone