Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution :

class Solution {

    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        int[][] dp = new int[nums.length][sum / 2 + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= sum / 2; j++) {
                dp[i][j] = -1;
            }
        }
        return equalSumPartition(nums, sum / 2, 0, dp) > 0;
    }

    /**
     * This method will return 1 if there is a subset with given sum else 0
     * Either we will pick the number or we will not pick the number for the subset sum
     *
     * @param nums  array of numbers
     * @param sum   sum to be found
     * @param index index of the array
     * @param dp    dp array
     * @return 1 if there is a subset with given sum else 0
     */
    public int equalSumPartition(int[] nums, int sum, int index, int[][] dp) {
        if (index > nums.length - 1) return 0;
        if (sum == 0) return 1;
        if (dp[index][sum] != -1) return dp[index][sum];
        if (nums[index] <= sum) {
            return dp[index][sum] = equalSumPartition(nums, sum - nums[index], index + 1, dp)
                    | equalSumPartition(nums, sum, index + 1, dp);
        } else {
            return dp[index][sum] = equalSumPartition(nums, sum, index + 1, dp);
        }
    }
}