Partition Equal Subset Sum — Medium Coding Interview Question

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of elements in both subsets is equal.

Example

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

Output: true

Explanation: [1,5,5] and [11].

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 100

Topics & Companies

Topics: dp, arrays

Asked by: Amazon, Google, Meta, Microsoft, Apple

Optimal Solution Complexity

Time complexity: O(n × target). Space complexity: O(target).

Practice more

• All DSA Problems
• DSA Patterns