Partition Equal Subset Sum
Problem Description
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.
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 <= 2001 <= nums[i] <= 100
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The problem can be seen as a variation of the 0/1 knapsack problem. The most basic approach is to use recursion to try every possible subset and check if there is a subset with a sum that is equal to half of the total sum of the array. We are using a recursive function that tries to include or exclude each number.
Code:
- Time Complexity: O(2^n) - where
nis the number of elements in the input array. This is due to the fact we have two choices (include/exclude) for each number. - Space Complexity: O(n) - due to the recursion stack used in recursive calls.
2. Memoization Approach
Intuition:
The recursive approach has an exponential time complexity because it recalculates results for the same subproblems multiple times. We can optimize it by storing intermediate results in a memoization table.
Code:
- Time Complexity: O(n * s) -
sis half of the total sum. - Space Complexity: O(n * s) - for the memoization table, and O(n) for the recursion stack.
3. Dynamic Programming Approach
Intuition:
We can solve the problem iteratively using dynamic programming with a boolean array. We aim to determine if we can form the subset with sum totalSum/2, by iteratively updating our possibilities in a boolean array.
Code:
- Time Complexity: O(n * s) - where
nis number of elements in the array andsis half the total sum of all elements. - Space Complexity: O(s) - this is space used by the
dparray.