Partition Equal Subset Sum

This approach explores all possible subsets of the given array nums using recursion. For each element, we make two choices: either include it in the current subset or not. We continue this process until we find a subset that sums up to the target value (half of the total sum) or exhaust all possibilities.

• Calculate the total sum of all elements in the nums array.
• If the total sum is odd, it's impossible to partition it into two equal halves, so return false.
• If the total sum is even, calculate the target sum, which is total_sum / 2.
• Define a recursive helper function, say canPartitionRecursive(index, target), that returns true if a subset summing to target can be formed using elements from nums[index] onwards.
• Base Cases for the recursion:
  • If target is 0, it means we have found a valid subset, so return true.
  • If target becomes negative or index goes beyond the array bounds, it's an invalid path, so return false.
• Recursive Step: For the element at nums[index], explore two choices:
  1. Include nums[index]: Make a recursive call canPartitionRecursive(index + 1, target - nums[index]).
  2. Exclude nums[index]: Make a recursive call canPartitionRecursive(index + 1, target).
• The result for the current state is true if either of the two choices returns true.
• The initial call to start the process is canPartitionRecursive(0, target).

First, we check a fundamental condition: if the total sum of all numbers in the array is odd, it's impossible to divide them into two subsets of equal sum. In this case, we can immediately return false. If the sum is even, we set our target to half of the total sum. The problem is now transformed into a search for a subset that adds up to this target.

We implement this search using a recursive function. This function explores every possible combination by making two recursive calls at each step for each number: one call that includes the current number in the subset (subtracting its value from the target) and another that excludes it (leaving the target unchanged). If any of these recursive paths eventually reduces the target to zero, it means we've found a valid partition, and we return true. If all paths are explored without finding such a subset, we return false.

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum % 2 != 0) {
            return false;
        }

        int targetSum = totalSum / 2;
        return canPartitionRecursive(nums, 0, targetSum);
    }

    private boolean canPartitionRecursive(int[] nums, int index, int target) {
        // Base case: If target is 0, we found a subset.
        if (target == 0) {
            return true;
        }

        // Base case: If we run out of numbers or target becomes negative.
        if (index >= nums.length || target < 0) {
            return false;
        }

        // Recursive step:
        // 1. Include the number at the current index.
        boolean include = canPartitionRecursive(nums, index + 1, target - nums[index]);
        
        // 2. Exclude the number at the current index.
        boolean exclude = canPartitionRecursive(nums, index + 1, target);

        return include || exclude;
    }
}