#0403Time: O(2^n), where `n` is the number of elements in `nums`. For each element, we have two choices, leading to an exponential number of paths to explore.Space: O(n), where `n` is the number of elements in the array. This space is used by the recursion call stack.9 companies
Given an integer array nums, return trueif 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 <= 200
1 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible subsets of the given array nums using recursion. For each element, we make two choices: either include it in the current subset or not. We continue this process until we find a subset that sums up to the target value (half of the total sum) or exhaust all possibilities.
Algorithm
Calculate the total sum of all elements in the nums array.
If the total sum is odd, it's impossible to partition it into two equal halves, so return false.
If the total sum is even, calculate the target sum, which is total_sum / 2.
Define a recursive helper function, say canPartitionRecursive(index, target), that returns true if a subset summing to target can be formed using elements from nums[index] onwards.
Base Cases for the recursion:
If target is 0, it means we have found a valid subset, so return true.
If target becomes negative or index goes beyond the array bounds, it's an invalid path, so return false.
Recursive Step: For the element at nums[index], explore two choices:
Include nums[index]: Make a recursive call canPartitionRecursive(index + 1, target - nums[index]).
Exclude nums[index]: Make a recursive call canPartitionRecursive(index + 1, target).
The result for the current state is true if either of the two choices returns true.
The initial call to start the process is canPartitionRecursive(0, target).
Walkthrough
First, we check a fundamental condition: if the total sum of all numbers in the array is odd, it's impossible to divide them into two subsets of equal sum. In this case, we can immediately return false. If the sum is even, we set our target to half of the total sum. The problem is now transformed into a search for a subset that adds up to this target.
We implement this search using a recursive function. This function explores every possible combination by making two recursive calls at each step for each number: one call that includes the current number in the subset (subtracting its value from the target) and another that excludes it (leaving the target unchanged). If any of these recursive paths eventually reduces the target to zero, it means we've found a valid partition, and we return true. If all paths are explored without finding such a subset, we return false.
1class Solution {2 public boolean canPartition(int[] nums) {3 int totalSum = 0;4 for (int num : nums) {5 totalSum += num;6 }78 if (totalSum % 2 != 0) {9 return false;10 }1112 int targetSum = totalSum / 2;13 return canPartitionRecursive(nums, 0, targetSum);14 }1516 private boolean canPartitionRecursive(int[] nums, int index, int target) {17 // Base case: If target is 0, we found a subset.18 if (target == 0) {19 return true;20 }2122 // Base case: If we run out of numbers or target becomes negative.23 if (index >= nums.length || target < 0) {24 return false;25 }2627 // Recursive step:28 // 1. Include the number at the current index.29 boolean include = canPartitionRecursive(nums, index + 1, target - nums[index]);3031 // 2. Exclude the number at the current index.32 boolean exclude = canPartitionRecursive(nums, index + 1, target);3334 return include || exclude;35 }36}
Complexity
Time
O(2^n), where `n` is the number of elements in `nums`. For each element, we have two choices, leading to an exponential number of paths to explore.
Space
O(n), where `n` is the number of elements in the array. This space is used by the recursion call stack.
Trade-offs
Pros
Simple to conceptualize and implement.
Follows a clear, divide-and-conquer logic.
Cons
Extremely inefficient due to its exponential time complexity.
Leads to a 'Time Limit Exceeded' error on most platforms for non-trivial inputs because it re-computes the same subproblems multiple times.
This approach, also known as Top-Down Dynamic Programming, optimizes the brute-force recursion by storing the results of subproblems. The recursive structure is the same, but we use a memoization table (e.g., a 2D array) to cache the result of each state (index, target). When the same subproblem is encountered again, we retrieve the result from the table instead of re-computing it, drastically reducing the number of calculations.
Algorithm
Calculate total_sum and target_sum as in the brute-force approach. Return false if total_sum is odd.
Create a memoization table, memo[n][target_sum + 1], where n is the number of elements. Initialize it with a value to signify 'not computed' (e.g., null or a specific integer like -1).
Use the same recursive helper function canPartitionMemo(index, target, memo).
Before any computation, check memo[index][target]. If the value has been computed, return it directly.
If not computed, perform the recursive calls as in the brute-force approach:
Store the computed result in memo[index][target] before returning it.
The initial call is canPartitionMemo(0, target_sum, memo).
Walkthrough
The brute-force approach suffers from solving the same subproblems repeatedly. For instance, finding if a sum of 50 can be made from elements [10, 20, ...] might be a subproblem reached through many different paths. Memoization addresses this by caching results.
We define a state by (index, target), representing the subproblem of finding if target sum can be achieved using elements from index onwards. We use a 2D array, memo, where memo[index][target] stores the boolean result. We can use an Integer[][] array where null means not computed, 1 means true, and 0 means false.
When the recursive function is called for a state (index, target), it first checks the memo table. If a result exists, it's returned immediately. Otherwise, the result is computed recursively, stored in the table, and then returned. This ensures that each unique subproblem is solved only once.
1class Solution {2 public boolean canPartition(int[] nums) {3 int totalSum = 0;4 for (int num : nums) {5 totalSum += num;6 }78 if (totalSum % 2 != 0) {9 return false;10 }1112 int targetSum = totalSum / 2;13 // memo[i][j] stores the result for canPartition(i, j)14 // null: not computed, 1: true, 0: false15 Integer[][] memo = new Integer[nums.length][targetSum + 1];1617 return canPartitionMemo(nums, 0, targetSum, memo);18 }1920 private boolean canPartitionMemo(int[] nums, int index, int target, Integer[][] memo) {21 if (target == 0) {22 return true;23 }24 if (index >= nums.length || target < 0) {25 return false;26 }2728 if (memo[index][target] != null) {29 return memo[index][target] == 1;30 }3132 // 1. Include the number at the current index.33 boolean include = canPartitionMemo(nums, index + 1, target - nums[index], memo);3435 // 2. Exclude the number at the current index.36 boolean exclude = canPartitionMemo(nums, index + 1, target, memo);3738 boolean result = include || exclude;39 memo[index][target] = result ? 1 : 0;40 return result;41 }42}
Complexity
Time
O(n * sum). The number of subproblems is `n * sum`, and each subproblem is computed once.
Space
O(n * sum), where `n` is the number of elements and `sum` is the target sum. This space is required for the memoization table. The recursion stack also adds O(n) space.
Trade-offs
Pros
Drastically more efficient than brute-force, with pseudo-polynomial time complexity.
Guarantees that each subproblem is solved only once.
Often retains the intuitive structure of the recursive solution.
Cons
The space complexity of O(n * sum) can be large if the target sum is high, potentially leading to memory issues.
While much faster than brute-force, it can be slightly slower than the iterative bottom-up approach due to recursion overhead.
This approach, also known as Bottom-Up Dynamic Programming, is the most optimized solution. It solves the problem iteratively and reduces the space complexity. We use a single 1D array, dp, where dp[j] indicates whether a sum of j can be formed. We iterate through each number in the input array and update this dp array to reflect the new sums that become possible by including the current number.
Algorithm
Calculate total_sum and target_sum. Return false if total_sum is odd.
Create a 1D boolean array dp of size target_sum + 1.
Initialize dp[0] = true, as a sum of 0 is always possible (with an empty set). All other dp[j] are implicitly false.
Iterate through each number num in the input nums array.
For each num, perform an inner loop that iterates backwards from j = target_sum down to num.
Inside the inner loop, update dp[j] with the rule: dp[j] = dp[j] || dp[j - num].
After iterating through all numbers, the answer is the value of dp[target_sum].
Walkthrough
This method builds the solution from the ground up. We determine all possible subset sums that can be formed and check if our target_sum is one of them.
We use a boolean array dp of size target_sum + 1. dp[j] = true means a subset with sum j exists. Initially, only dp[0] is true.
We then process each number num from the input array one by one. For each num, we want to update our dp array. If we can form a sum j - num, then by adding num, we can now form the sum j. So, the new dp[j] should be true if the old dp[j] was true OR if dp[j - num] was true.
To implement this correctly and avoid using the same number multiple times in a single subset sum (which would be the 'unbounded knapsack' problem), we must iterate the inner loop (for sums j) backwards. By iterating from target_sum down to num, when we calculate dp[j], the value dp[j - num] we use is from before we considered the current num in this pass. This correctly models the 0/1 knapsack logic where each item is used at most once.
After iterating through all numbers, dp[target_sum] will hold the final answer.
1class Solution {2 public boolean canPartition(int[] nums) {3 int totalSum = 0;4 for (int num : nums) {5 totalSum += num;6 }78 if (totalSum % 2 != 0) {9 return false;10 }1112 int targetSum = totalSum / 2;1314 boolean[] dp = new boolean[targetSum + 1];15 dp[0] = true;1617 for (int num : nums) {18 for (int j = targetSum; j >= num; j--) {19 dp[j] = dp[j] || dp[j - num];20 }21 }2223 return dp[targetSum];24 }25}
Complexity
Time
O(n * sum). The two nested loops iterate `n` times and `sum` times, respectively.
Space
O(sum), where `sum` is the target sum. This is a significant improvement over the O(n * sum) space of the 2D DP/memoization approaches.
Trade-offs
Pros
Most efficient in terms of space complexity.
Iterative approach avoids recursion overhead and the risk of stack overflow.
Generally the fastest practical solution for this problem's constraints.
Cons
The logic, especially the backward iteration, can be less intuitive to grasp compared to the recursive approaches.
The time complexity is still dependent on the target sum, making it pseudo-polynomial.
Solutions
Solution
1import java.util.Arrays ; public class Partition_Equal_Subset_Sum { public static void main ( String [] args ) { Partition_Equal_Subset_Sum out = new Partition_Equal_Subset_Sum (); Solution s = out . new Solution (); System . out . println ( s . canPartition ( new int []{ 1 , 5 , 11 , 5 })); System . out . println ( s . canPartition ( new int []{ 1 , 2 , 3 , 5 })); } class Solution { public boolean canPartition ( int [] nums ) { if ( nums == null || nums . length == 0 ) { return false ; } // in case overflow, should use long int sum = sum = Arrays . stream ( nums ). sum (); if ( sum % 2 != 0 ) { // two equal subsets, then sum must be 2*x return false ; } int target = sum / 2 ; // dp[i] 表示原数组是否可以取出若干个数字，其和为i boolean [] dp = new boolean [ target + 1 ]; dp [ 0 ] = true ; for ( int i = 0 ; i < nums . length ; i ++) { for ( int v = target ; v >= nums [ i ]; v --) { dp [ v ] = dp [ v ] || dp [ v - nums [ i ]]; } } return dp [ target ]; } } class Solution_Bitset { /* bool canPartition(vector<int>& nums) { bitset<5001> bits(1); int sum = accumulate(nums.begin(), nums.end(), 0); for (int num : nums) bits |= bits << num; return (sum % 2 == 0) && bits[sum >> 1]; } */ } // only when subset has 2 elements class Solution_2sum { public boolean canPartition ( int [] nums ) { if ( nums == null || nums . length == 0 ) { return false ; } // in case overflow long sum = Arrays . stream ( nums ). reduce ( 0 , ( x , y ) -> ( x + y )); if ( sum % 2 == 1 ) { return false ; // two equal subsets, then sum must be 2*x } // then it's 2Sum question to sum/2 Two_Sum twoSum = new Two_Sum (); Two_Sum . Solution twoSumSolution = twoSum . new Solution (); Arrays . sort ( nums ); // possible overflow return twoSumSolution . twoSum ( nums , ( int ) sum / 2 ) == null ; } } } ////// class Solution { public boolean canPartition ( int [] nums ) { int s = 0 ; for ( int v : nums ) { s += v ; } if ( s % 2 != 0 ) { return false ; } int n = s >> 1 ; boolean [] dp = new boolean [ n + 1 ]; dp [ 0 ] = true ; for ( int v : nums ) { for ( int j = n ; j >= v ; -- j ) { dp [ j ] = dp [ j ] || dp [ j - v ]; } } return dp [ n ]; } }
1/** * @param {number[]} nums * @return {boolean} */ var canPartition =2 function (nums) {3 let s = 0;4 for (let v of nums) {5 s += v;6 }7 if (s % 2 != 0) {8 return false;9 }10 const m = nums.length;11 const n = s >> 1;12 const dp = new Array(n + 1).fill(false);13 dp[0] = true;14 for (let i = 1; i <= m; ++i) {15 for (let j = n; j >= nums[i - 1]; --j) {16 dp[j] = dp[j] || dp[j - nums[i - 1]];17 }18 }19 return dp[n];20 };
1class Solution:2 def canPartition(self, nums: List[int]) -> bool: s = sum(nums) if s % 2 != 0: return False n = s >> 1 dp = [False] * (n + 1) dp[0] = True for v in nums: for target in range(n, v - 1, - 1): # including v itself dp [ target ] = dp [ target ] or dp [ target - v ] return dp [ - 1 ] class Solution : # recursive, but over time limit in OJ def canPartition ( self , nums : List [ int ]) -> bool : total_sum = sum ( nums ) if total_sum % 2 != 0 : return False target_sum = total_sum // 2 memo = {} # ==> or just use @cache for dfs() def dfs ( idx , curr_sum ): if curr_sum == target_sum : return True if curr_sum > target_sum or idx >= len ( nums ): return False if ( idx , curr_sum ) in memo : return memo [( idx , curr_sum )] # Explore two options: include the current number or exclude it include = dfs ( idx + 1 , curr_sum + nums [ idx ]) exclude = dfs ( idx + 1 , curr_sum ) memo [( idx , curr_sum )] = include or exclude return memo [( idx , curr_sum )] return dfs ( 0 , 0 ) ############ class Solution : def canPartition ( self , nums : List [ int ]) -> bool : m , mod = divmod ( sum ( nums ), 2 ) if mod : return False f = [ True ] + [ False ] * m for x in nums : for j in range ( m , x - 1 , - 1 ): f [ j ] = f [ j ] or f [ j - x ] return f [ m ]
1// OJ: https://leetcode.com/problems/partition-equal-subset-sum/ // Time: O(2^N) // Space: O(2^N) class Solution { public: bool canPartition ( vector < int >& A ) { int total = accumulate ( begin ( A ), end ( A ), 0 ); if ( total % 2 ) return false ; unordered_set < int > s , next ; for ( int n : A ) { next = s ; for ( int m : s ) next . insert ( m + n ); next . insert ( n ); if ( next . count ( total / 2 )) return true ; swap ( s , next ); } return false ; } };
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
