Saved from https://leetcode.com/problems/partition-equal-subset-sum/

lc416

class Solution {
    // We maintain a 2D array , dp[n][subSetSum] 
    // For an array element i and sum j in array nums,
    // dp[i][j]=true if the sum j can be formed by array elements 
    // in subset nums[0]..nums[i], otherwise dp[i][j]=false
    //
    // Time: O(n * sum)
    // Space: O(n * sum)
    public boolean canPartition(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        if (totalSum % 2 != 0) 
            return false;
        boolean[][] dp = new boolean[nums.length+1][totalSum / 2 + 1];
        dp[0][0] = true;
        int prefixSum = 0;
        for (int i = 1; i < nums.length + 1; i++) {
            int num = nums[i-1];
            prefixSum += num;
            for (int j = 0; j < dp[0].length; j++) {
                if (dp[i-1][j] || (j-num >= 0 && dp[i-1][j-num])) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[nums.length][dp[0].length - 1];
    }
}