Partition Equal Subset Sum — Leetcode 416

Original problem link: https://leetcode.com/problems/partition-equal-subset-sum/description/

In this problem, we’re given an array of numbers and asked if we are able to partition it into two subsets of equal sums.

This is a DP problem, since we need to check the possibility of including or not including each element.

Thus we come up with this solution.

class Solution {

    Boolean[][] cache;

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (sum % 2 == 1) {
            return false;
        }

        cache = new Boolean[nums.length + 1][(sum / 2) + 1];

        return dp(nums, 0, 0, sum / 2);
    }

    private boolean dp(int[] nums, int index, int sum, int desired) {
        if (sum == desired) {
            return true;
        }
        if (sum > desired || index == nums.length) {
            return false;
        }
        if (cache[index][sum] != null) {
            return cache[index][sum];
        }

        boolean result = dp(nums, index + 1, sum + nums[index], desired) || dp(nums, index + 1, sum, desired);
        cache[index][sum] = result;
        return result;
    }
}

The runtime is 28 ms and beats 91% of submissions.