Practice/Google/Leetcode 416. Partition Equal Subset Sum

Leetcode 416. Partition Equal Subset Sum

CodingMust

Problem

Given an array of positive integers, determine whether it's possible to divide the array into two subsets such that the sum of elements in both subsets is equal.

Your task is to return true if such a partition exists, and false otherwise.

Requirements

1. Return a boolean indicating whether an equal sum partition is possible
2. Each element must belong to exactly one subset
3. Both subsets must be non-empty
4. The order of elements within subsets doesn't matter

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 100
• You should aim for a solution with reasonable time complexity for the given constraints

Examples

Example 1:

Input: nums = [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11], both with sum 11.

Example 2:

Input: nums = [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into two subsets with equal sum. The total sum is 11, which is odd.

Example 3:

Input: nums = [2, 2, 1, 1] Output: true Explanation: The array can be partitioned as [2, 1] and [2, 1], both with sum 3.