LeetCode 416. Partition Equal Subset Sum

partition-equal-subset-sum.java

/**
 * https://leetcode.com/problems/partition-equal-subset-sum/
 *
 * O(m * n) runtime, O(m * n) space, where m is the number of elements in the array, and n is the sum of elements
 *
 * this question could become the typical backpack question with proper definition of the state
 *
 * 1. state
 *   state[i][j] means that
 *     if it is possible to find a subset of the set whose members are the first i elements of the array
 *     such that the sum of elements in the subset is j
 * 2. function
 *   state[i][j] = state[i-1][j] || state[i-1][j-nums[i]]
 * 3. initialization
 *   state[0][0] is true which means it is possible to get 0 using first 0 element
 * 4. answer
 *   state[m][n]
 */

public class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        int row = nums.length + 1;
        int col = sum + 1;
        boolean[][] cache = new boolean[row][col];
        cache[0][0] = true;
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (cache[i-1][j] || (j-nums[i-1] >= 0 && cache[i-1][j-nums[i-1]])) { // the i-th element is nums[i-1] here
                    cache[i][j] = true;
                }
            }
        }
        return cache[row-1][col-1];
    }
}