• Difficulty: Medium

---

Problem Definition

Given an array of integers, write a function to determine if the array can be split into 2 subsets with equal sums. This is similar to Balanced Split of an Array of Numbers, but, in this case, the partitioning can include elements from all over the array instead of either before or after a specific index in the array.

---

Examples

Some test cases to verify our solution.

assert equal_partition([1, 2, 5, 6]) # because sum([1, 6]) == sum([2, 5])
assert equal_partition([4, 13, 1, 4, 4]) # because sum([13]) == sum([4, 1, 4, 4])
assert not equal_partition([2, 5, 7, 3])

---

Recursive Solution

We want to determine if there is a subset that is equal to half the sum of the whole array. So for every element, we can either include the element in the subset or exclude it, creating a binary branch for each element.

def helper(arr, idx, target, arr_len):
    if idx >= arr_len:
        return False
    if target == 0 or arr[idx] == target:
        return True
    return helper(arr, idx + 1, target, arr_len) or helper(arr, idx + 1, target - arr[idx], arr_len)

def equal_partition(arr):
    total = sum(arr)
    if total % 2 == 1: # no balanced split possible if arr sum is odd
        return False
    target = total / 2
    arr_len = len(arr)
    return helper(arr, 1, target, arr_len) or helper(arr, 1, target - arr[0], arr_len)

---

Complexity

Let $n = $ len(arr).

Runtime complexity should be $O(2^n)$ since we are branching twice at each element.

Auxiliary space complexity should be $O(log(n))$ because we'll have $log(n)$ stack frames of helper at certain points.

---

Generative Solution

The solution above wastes a lot of space and effort on computing bad branches. E.g., the path that chooses no elements for inclusion in the subset is a waste.

We can improve the average and mean runtime for some cases by constructing all possible sums. But this solution won't improve the worst case runtime or space because, in the worst case, the sum is not possible and we need to check every possible sum.

However, this will come at a higher space cost because we will be storing each possible sum.

def equal_partition(arr):
    sums = set([0])
    total = sum(arr)
    if total % 2 == 1:
        return False
    target = total / 2
    for item in arr:
        to_add = set()
        for prev_sum in sums:
            new_sum = prev_sum + item
            if new_sum == target:
                return True
            to_add.add(new_sum)
        sums.update(to_add)
    return False