Given an array of integers and a target sum, find all subsets whose sum is equal to the target sum.

Find All Subsets with a Given Sum

• Description: Given an array of integers and a target sum, find all subsets whose sum is equal to the target sum.
• Input: An array of integers arr[] and a target sum target.
• Output: Return a list of lists containing all subsets that sum up to the target sum.
• Example:
  • Input: arr = [1, 2, 3, 3], target = 6
  • Output: [[1, 2, 3], [3, 3]]

 

Find All Subsets with a Given Sum

java
import java.util.ArrayList;
import java.util.List;

public class AllSubsetsWithSum {
    public static List<List<Integer>> findSubsets(int[] arr, int target) {
        List<List<Integer>> result = new ArrayList<>();
        findSubsetsRecursive(arr, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void findSubsetsRecursive(int[] arr, int target, int index, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (index == arr.length) return;

        // Include the current element
        if (arr[index] <= target) {
            current.add(arr[index]);
            findSubsetsRecursive(arr, target - arr[index], index + 1, current, result);
            current.remove(current.size() - 1);
        }

        // Exclude the current element
        findSubsetsRecursive(arr, target, index + 1, current, result);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3};
        int target = 6;
        List<List<Integer>> subsets = findSubsets(arr, target);
        for (List<Integer> subset : subsets) {
            System.out.println(subset);
        }
        // Output: [1, 2, 3], [3, 3]
    }
}