3.Equal Sum Partition

Intuition & Approach Understanding the problem: If an array can be divided into two subsets with equal sum, the total sum of the array must be even. If the total sum is odd, it is impossible to divide it into two equal halves. Otherwise, we need to check if a subset exists with a sum of sum/2 (because the second subset will naturally have the same sum). Dynamic Programming Approach: We use a boolean DP table dp[i][j] where: dp[i][j] = true → A subset of the first i elements can form sum j. Base Cases: dp[i][0] = true (sum 0 is always possible with an empty subset). dp[0][j] = false for j > 0 (if no elements, we cannot form a positive sum). Transition Formula: If nums[i-1] <= j: dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]] Otherwise, exclude the current element: dp[i][j] = dp[i-1][j] The answer is stored in dp[n][sum/2]. Optimized Java Code public class EqualSumPartition { public static boolean isSubsetExists(int[] nums, int n, int sum) { boolean dp[][] = new boolean[n + 1][sum + 1];

    // Base case: If sum = 0, subset always exists
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    // If we have 0 elements, no subset can form a positive sum
    for (int j = 1; j <= sum; j++) {
        dp[0][j] = false;
    }

    // DP Table Filling
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (nums[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][sum];
}

public static boolean isEqualSumPartitionPossible(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;

    // If total sum is odd, we cannot divide into equal subsets
    if (sum % 2 != 0) return false;

    // Check if a subset with sum = sum/2 exists
    return isSubsetExists(nums, nums.length, sum / 2);
}

public static void main(String[] args) {
    int[] arr = {2, 4, 6};
    System.out.println("Is Equal Sum Partition Possible? " + isEqualSumPartitionPossible(arr));
}

} Explanation with Example Input:

int[] arr = {2, 4, 6}; Steps:

Calculate total sum → 2 + 4 + 6 = 12 Check if sum is even → Yes (12 % 2 == 0), so we proceed. Find subset with sum 12/2 = 6: Possible subset: {2, 4} ✅ Output: Is Equal Sum Partition Possible? true Time & Space Complexity Time Complexity: O(n * sum/2) Space Complexity: O(n * sum/2) ✅ Optimized DP-based approach ✅ Clear explanation ✅ Efficient solution