Back to ChallengesPartition Equal Subset SumMedium 25 min

Partition Equal Subset Sum

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

Input: nums = [1,5,11,5]

Output: true

Can be partitioned as [1, 5, 5] and [11].

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

Output: false

Cannot be partitioned equally.

Constraints

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

Complexity Analysis

Time

O(n * target)

where target is sum / 2.

Space

O(target)

space optimized DP array.

Test Cases

#1 Can partition

Input: [1,5,11,5]

Expected: true

#2 Cannot partition

Input: [1,2,3,5]

Expected: false

JavaScript

Output

Click "Run Code" to see output here...