class Solution {
    public int[][] remain;
    
    public int sum(int[] arr) {
        int total = 0;
        for (int data : arr) {
            total += data;
        }
        
        return total;
    }
    
    /*
        Since we are finding if there is a way to partition the set 
            into 2 subsets that have equal sum (let's call it x1 and x2)
            then we can check if there is a subset that has 
            the sum equal to half
        Because x1 = x2 and x1 + x2 = total => x1 = x2 = total / 2
    */
    
    /*
        To find if there is a subset that can be sum up to a certain number,
            the idea is have a 2d array[][] where arr[i][j] represents
                if we haven't gone through that path (0), 
                can't be summed up to sum (-1),
                can be summed up to sum (1).
        We can then search for by going: 
            arr[half][i] -> arr[half - i][i'] -> ... until arr[n][m] = 0
            where i, i', m belongs to nums[]
    */
    public boolean canPartition(int[] nums) {
        int total = sum(nums);
        //Meaningless if the total is odd
        if (total % 2 != 0) {
            return false;
        }
        
        int half = total / 2;   //Find half of the total sum
        remain = new int[half + 1][nums.length];
        
        //Fill the base cases
        for (int indx = 0; indx < nums.length; indx++) {
            remain[0][indx] = 1;
        }
        
        //Fill out the rest
        fillTable(nums, half, nums.length - 1);
        
        boolean found = false;
        for(int data : remain[half]) {
            if (data == 1) {
                found = true;
                break;
            }
        }
        
        //Check if there is a subset that has the sum equals to that half
        return found;
    }
    
    public boolean fillTable(int[] nums, int curSum, int index) {
        if (curSum < 0 || index < 0) {
            //Invalid
            return false;
        } 
        
        //No need to check again
        if (remain[curSum][index] != 0) {
            return remain[curSum][index] == 1 ? true : false;    
        }
        
        //Default
        remain[curSum][index] = -1;
        boolean found = false;
        
        for (int indx = index; indx > -1 && found != true; indx--) {
            found = fillTable(nums, curSum - nums[indx], indx - 1);
        }    
        
        if (found == true) {
            remain[curSum][index] = 1;    
        }
        
        return found;
    }
    
}