416. Partition Equal Subset Sum
Partition Equal Subset Sum (LeetCode 416) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (0/1 Knapsack Subset Sum Style) subpattern.
- NeetCode 150 · #110 of 150 · 1-D Dynamic Programming
- NeetCode 250 · #186 of 250 · 1-D Dynamic Programming
How to solve Partition Equal Subset Sum
Partition Equal Subset Sum is a 0/1 Knapsack and Subset Sum problem, part of Dynamic Programming (DP) Patterns. Solve 0/1 knapsack, partition equal subset sum, and target sum problems.
Work towards the solution in these steps:
- Think about whether the array can be split into two subsets with equal sum by focusing on the sum properties of the array.
- Consider the problem as finding a subset of the array whose sum is half of the total sum, if the total sum is even.
- Use dynamic programming to determine if a subset with a particular sum exists; this relates to the classic subset sum problem.
The reference solution runs in O(n * s) time and O(s) space.
The Partition Equal Subset Sum solution and editorial walks through the full approach with reference code.
Problem statement
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 <= 200
- 1 <= nums[i] <= 100
Topics and companies
Topics: Array, Dynamic Programming.
Reported in interviews at Amazon, Facebook, Google, Microsoft.
How to practise Partition Equal Subset Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * s) time and O(s) space.
Open Partition Equal Subset Sum in the code editor, or read the Partition Equal Subset Sum editorial for a worked solution with its approach and complexity analysis.
Where Partition Equal Subset Sum sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 1D Array (0/1 Knapsack Subset Sum Style) subpattern
- The full DSA patterns sheet
Problems related to Partition Equal Subset Sum
Other problems that use the same 1D Array (0/1 Knapsack Subset Sum Style) and Dynamic Programming (DP) Patterns techniques:
- Last Stone Weight II — Medium, same subpattern
- Target Sum — Medium, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
- Best Time to Buy and Sell Stock IV — Hard, same pattern
Partition Equal Subset Sum FAQ
What is the LeetCode number of Partition Equal Subset Sum?
Partition Equal Subset Sum is LeetCode problem 416, rated Medium.
What pattern is used to solve Partition Equal Subset Sum?
Partition Equal Subset Sum is a 0/1 Knapsack and Subset Sum problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (0/1 Knapsack Subset Sum Style) subpattern.
What is the time complexity of Partition Equal Subset Sum?
The reference solution runs in O(n * s) time and O(s) space.
Which companies ask Partition Equal Subset Sum?
Partition Equal Subset Sum has been reported in interviews at Amazon, Facebook, Google, Microsoft.