2-D Dynamic Programming Knapsack
547. Partition Equal Subset Sum
Medium 147 DSA Sheet
You are given an array of positive integers nums. Split it into two groups so that every element goes into
exactly one group. The groups do not have to be contiguous or the same size.
Return true if some split gives the two groups equal sums, and false otherwise.
Example 1
Input: nums = [6, 2, 9, 4, 5]
Output:
trueExplanation: The groups [9, 4] and [6, 2, 5] both sum to 13.
Example 2
Input: nums = [2, 8, 4]
Output:
falseExplanation: The total is 14, so each group would need 7. Every number is even, so no group can sum to 7.
Example 3
Input: nums = [7, 3, 1, 4, 2]
Output:
falseExplanation: The total is 17. An odd total cannot be split into two equal whole numbers.
Check your understanding
Work out the answer for this input before you write any code.
nums = [3, 3, 2, 2, 2]
Constraints
1 ≤ nums.length ≤ 1001 ≤ nums[i] ≤ 200
Clarifying questions
What you would ask an interviewer before writing any code.