Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.

2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums)
            sum += x;
        if (sum % 2 != 0)
            return false;
        int n = nums.length;
        // using subset sum problem to find a subset which has sum = total sum/2
        boolean dp[][] = new boolean[n + 1][sum / 2 + 1];
        // base case when sum->0 then answer is always true
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;
        // dp[i][k] -> tells us if it is possible to form a subsequence from (0,i) with
        // sum=k
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= sum / 2; k++) {
                if (k - nums[i - 1] >= 0)
                    dp[i][k] = dp[i - 1][k] || dp[i - 1][k - nums[i - 1]];
                else
                    dp[i][k] = dp[i - 1][k];
            }
        }
        return dp[n][sum / 2];
    }
}