Equal Partitions

Description

Given a list of positive integers nums, return whether you can partition nums into two groups where the sum of the elements in both groups is equal.

Constraints:

• n ≤ 250
• 1 ≤ nums[i] ≤ 100

Example 1

Input

nums = [1, 2, 5, 4]

Output

true

Explanation

We can have these partitions: [1, 5] and [2, 4].

---

Intuition

1. make sure the sum of array is even
2. Backtracking

Implementation

import java.util.*;

class Solution {
    public boolean solve(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        } else {
            return canSplit(0, sum / 2 - nums[0], nums);
        }
    }

    private boolean canSplit(int index, int target, int[] nums) {
        if (target == 0) {
            return true;
        } else if (target < 0) {
            return false;
        }
        for (int i = index + 1; i < nums.length; i++) {
            if (canSplit(i, target - nums[i], nums)) {
                return true;
            }
        }
        return false;
    }
}

Time Complexity

• Time: O(nlogn)
• Space:O(logn)