416. Partition Equal Subset Sum

Solution.java

package dev.namtx.leetcode;

import java.util.Arrays;

public class PartitionEqualSubsetSum {
    public static final int UNCALCULATED = -1;
    public static final int IMPOSSIBLE = 1;
    public static final int POSSIBLE = 0;

    public static void main(String[] args) {
        System.out.println(new PartitionEqualSubsetSum().canPartition(new int[]{1, 5, 11, 5}));
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;

        if (sum % 2 != 0) return false;

        int[][] dp = new int[nums.length][sum / 2 + 1];
        for (int i = 0; i < nums.length; i++) Arrays.fill(dp[i], UNCALCULATED);

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

    private boolean subsetSum(int[] nums, int[][] dp, int sum, int i) {
        if (sum == 0) return true;

        if (i == nums.length || sum < 0) return false;

        if (dp[i][sum] != UNCALCULATED) return dp[i][sum] == POSSIBLE;

        dp[i][sum] = (subsetSum(nums, dp, sum - nums[i], i + 1) || subsetSum(nums, dp, sum, i + 1)) ? POSSIBLE : IMPOSSIBLE;

        return dp[i][sum] == POSSIBLE;
    }
}

Solution.md

Approach

• Dynamic programming

First of all, we calculate the sum as sum of all number of nums. We have some conclusions as following:

• if nums % 2 != 0, we can immediatly return `false
• otherwise, we can turn this problem into find a subset of nums which have total of its element equal to sum / 2.
• when we examine a element at i, there are two cases:
  • nums[i] belongs to the subset
  • nums[i] doesn't belong to the subset
• if yes, recursive on the remaining elements of nums and find a subset have a new total = nums / 2 - nums[i]
• if no, recursive on the remaing elemetns of nums and find a subset have a new total = nums / 2

DP and Brute force

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;

        if (sum % 2 != 0) return false;

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

    private boolean subsetSum(int[] nums, int sum, int i) {
        if (sum == 0) return true;

        if (i == nums.length || sum < 0) return false;

        return subsetSum(nums, sum - nums[i], i + 1) || subsetSum(nums, sum, i + 1);
    }
}

❌ TLE 😢

We can improve above solution by using a dp table to memorize the duplicate calculations.

Submission