Given an array of integers, determine if there is a subset with a sum equal to a given target sum.

 

Description: Given an array of integers, 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 sum equal to the target sum; otherwise, return false.

Example:

• Input: arr = [3, 34, 4, 12, 5, 2], target = 9
• Output: true (Subset [3, 4, 2] has a sum of 9)
  
  
  

Solution:

Basic Subset Sum Problem

java:
import java.util.*;

public class SubsetSum {
    public static boolean isSubsetSum(int[] arr, int target) {
        boolean[][] dp = new boolean[arr.length + 1][target + 1];
        
        // Initialize
        for (int i = 0; i <= arr.length; i++) {
            dp[i][0] = true;
        }
        
        // Fill the dp table
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (arr[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return dp[arr.length][target];
    }

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