416. Partition Equal Subset Sum!

class Solution {
    public boolean canPartition(int[] nums) {
        //dp[i][j] represent if the first ith elements in nums have a sum of j;
        //dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j]
        
        // calculate the larget j needed;
        int sum = 0;
        for (int num : nums){
            sum+=num;
        }
        if (sum%2==1) return false;
        
        // remember: boolean
        boolean[][] memo = new boolean[nums.length+1][sum/2+1];
        
        //initialize: if no elements, then sum is 0
        memo[0][0]=true;
        
        for(int i=1; i<=nums.length; i++){
            // i represent the first ith elements in nums, the last element index shuld be i-1;
            int curr = nums[i-1];
            for (int j=0; j<=sum/2; j++){
                // since current reuslt only relies on the result of previous row,
                // memory can be optimized
                memo[i][j] = (j-curr<0 ? false : memo[i-1][j-curr]) || memo[i-1][j];
            }
        }
        return memo[nums.length][sum/2];
    }
}