Given an array of integers that can include negative numbers, determine if there is a subset with a sum equal to a given target sum.

Subset Sum Problem with Negative Numbers

• Description: Given an array of integers that can include negative numbers, determine if there is a subset with a sum equal to a given target sum.
• Input: An array of integers arr[] and a target sum target.
• Output: Return true if there is a subset with a sum equal to the target sum; otherwise, return false.
• Example:
  • Input: arr = [-1, 2, 3, 4], target = 6
  • Output: true (Subset [-1, 2, 3, 4] has a sum of 6)

 

Solution:

Subset Sum Problem with Negative Numbers

java
public class SubsetSumWithNegatives {
    public static boolean isSubsetSum(int[] arr, int target) {
        int sum = Arrays.stream(arr).sum();
        if (target > sum || (sum + target) % 2 != 0) return false;
        target = (sum + target) / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : arr) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        int[] arr = {-1, 2, 3, 4};
        int target = 6;
        System.out.println(isSubsetSum(arr, target)); // Output: true
    }
}