Given an array of integers and a target sum, find the number of subsets that sum up to the target sum.

 

Description: Given an array of integers and a target sum, find the number of subsets that sum up to the target sum.

Input: An array of integers arr[] and a target sum target.

Output: Return the number of subsets with a sum equal to the target sum.

Example:

• Input: arr = [1, 2, 3, 3], target = 6
• Output: 2 (Subsets [1, 2, 3] and [3, 3] have a sum of 6)

Solution:

1. Count of Subsets with Given Sum

   java
   public class SubsetSumCount {
       public static int countSubsets(int[] arr, int target) {
           int[][] dp = new int[arr.length + 1][target + 1];
           
           // Initialize
           for (int i = 0; i <= arr.length; i++) {
               dp[i][0] = 1;
           }
           
           // 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 = {1, 2, 3, 3};
           int target = 6;
           System.out.println(countSubsets(arr, target)); // Output: 2
       }
   }