791. Partition Equal Subset Sum (Recursive + Memo)

Given an array of positive integers nums, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal. Return true if possible, false otherwise. Implement with recursion + memoization. This reduces to checking if any subset sums to totalSum / 2.

Input: An integer array nums of positive integers.

Output: Return a boolean: true or false.

Examples

Input: [1,5,11,5]
Output: true
Explanation: {1,5,5} and {11} both sum to 11.

Input: [1,2,3,5]
Output: false
Explanation: Sum is 11, which is odd.

Input: [1,1]
Output: true
Explanation: {1} and {1}.

Constraints

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

Asked by