medium Subset Sum Equal to Target

Problem Statement

Given an array nums containing n integers, return the number of subsets having a sum equal to x.

A subset can be any combination of numbers from the array, including an empty subset. However, you need to consider all possible combinations to determine the exact number of subsets with a sum equal to x.

Examples

Example 1:

• Input: nums = [1, 2, 3, 4, 5], x = 5
• Expected Output: 3
• Explanation: The subsets that sum to 5 are [5], [1, 4], and [2, 3].

Example 2:

• Input: nums = [2, 4, 6, 10], x = 16
• Expected Output: 2
• Explanation: The subsets that sum to 16 are [6, 10] and [2, 4, 10].

Example 3:

• Input: nums = [7, -3, 2, 5, 1], x = 9
• Expected Output: 2
• Explanation: The subsets that sum to 9 are [7, 2] and [-3, 7, 5].

Solution

To solve the "Subset sum equal to x" problem efficiently, we use the "Meet in the Middle" approach, which reduces the problem size by splitting the array into two halves. The key idea is to generate all possible subset sums for each half of the array. This allows us to handle each half independently, making the problem more manageable. By doing so, we turn a potentially large problem into two smaller problems, each with a reduced number of elements. This significantly cuts down the number of subsets we need to consider.

After generating the subset sums for both halves, we sort the sums from the second half. This sorting step is crucial because it enables us to use binary search to quickly find complementary sums. For each sum in the first half, we calculate the required complementary sum that, when added together, equals the target x. We then use binary search to efficiently count how many times this complementary sum appears in the sorted list from the second half. This method is effective because it leverages the power of sorting and binary search to reduce the time complexity, making it more feasible to solve the problem even for larger inputs.

Step-by-Step Algorithm

1. Initialization:

   • Define n to store the length of nums.

2. Splitting the Array:

   • Split the input array nums into two halves:
     • left will contain the first n/2 elements of nums.
     • right will contain the remaining elements of nums.

3. Generating Subset Sums for left:

   • Initialize an empty list leftSums to store the sums of all possible subsets of left.
   • Calculate the total number of subsets for left. Since left has n/2 elements, there are 2^(n/2) possible subsets.
   • Iterate through all possible subsets using a bitmask approach:
     • For each possible subset, represented by an integer i ranging from 0 to 2^(n/2) - 1, do the following:
       • Initialize a variable sum to 0 to store the sum of the current subset.
       • For each bit j in the binary representation of i:
         • If the j-th bit of i is set (i.e., i & (1 << j) != 0), include the j-th element of left in the subset and add it to sum.
       • After processing all bits, add the calculated sum to leftSums.
   • The list leftSums now contains the sums of all possible subsets of the left half of the array.

4. Generating Subset Sums for right:

   • Initialize an empty list rightSums to store the sums.
   • Repeat the same process as in step 3 for right and store the sums in rightSums.

5. Sorting rightSums:

   • Sort the list rightSums in non-decreasing order. Sorting is necessary to enable efficient binary search operations in the next step.

6. Counting Valid Subsets:

   • Initialize a variable count to 0 to keep track of the number of valid subsets whose sum equals x.
   • For each sum leftSum in leftSums, do the following:
     • Calculate the complementary sum needed to reach x by subtracting leftSum from x (i.e., complement = x - leftSum).
     • Use binary search on the sorted list rightSums to find how many times complement appears in rightSums. This gives the number of valid subsets in right that, when combined with the subset from left, will sum to x.
     • Add this count to the total count.

7. Output:

   • Return the value of count, which represents the total number of subsets across both halves that sum to x.

Algorithm Walkthrough

Let's go through the algorithm step by step using the provided example:

1. Input:

   • Array nums = [1, 2, 3, 4, 5]
   • Target x = 5
   • Length n = 5

2. Splitting the Array:

   • left = [1, 2]
   • right = [3, 4, 5]

3. Generating Subset Sums for left:

   • Subsets of left = [1, 2] are:
     • Subset {}: Sum = 0
     • Subset {1}: Sum = 1
     • Subset {2}: Sum = 2
     • Subset {1, 2}: Sum = 3
   • leftSums = [0, 1, 2, 3]

4. Generating Subset Sums for right:

   • Subsets of right = [3, 4, 5] are:
     • Subset {}: Sum = 0
     • Subset {3}: Sum = 3
     • Subset {4}: Sum = 4
     • Subset {5}: Sum = 5
     • Subset {3, 4}: Sum = 7
     • Subset {3, 5}: Sum = 8
     • Subset {4, 5}: Sum = 9
     • Subset {3, 4, 5}: Sum = 12
   • rightSums = [0, 3, 4, 5, 7, 8, 9, 12]

5. Sorting rightSums:

   • rightSums is already sorted, so no changes are needed.

6. Counting Valid Subsets:

   • Initialize count = 0.
   • For leftSum = 0:
     • complement = 5 - 0 = 5
     • Use binary search to find occurrences of 5 in rightSums, which is 1.
     • Increment count by 1. (count = 1)
   • For leftSum = 1:
     • complement = 5 - 1 = 4
     • Use binary search to find occurrences of 4 in rightSums, which is 1.
     • Increment count by 1. (count = 2)
   • For leftSum = 2:
     • complement = 5 - 2 = 3
     • Use binary search to find occurrences of 3 in rightSums, which is 1.
     • Increment count by 1. (count = 3)
   • For leftSum = 3:
     • complement = 5 - 3 = 2
     • Use binary search to find occurrences of 2 in rightSums, which is 0.
     • No change to count. (count = 3)

7. Output:

   • The final result is count = 3, which matches the expected output.

Code

import java.util.*;

public class Solution {

    // Method to find the number of subsets that sum up to the target x using the meet in the middle approach
    public int countSubsets(int[] nums, int x) {
        int n = nums.length;

        // Split the array into two halves
        int[] left = Arrays.copyOfRange(nums, 0, n / 2);
        int[] right = Arrays.copyOfRange(nums, n / 2, n);

        // Generate all possible subset sums for each half
        List<Integer> leftSums = generateSubsetSums(left);
        List<Integer> rightSums = generateSubsetSums(right);

        // Sort the right sums to use binary search
        Collections.sort(rightSums);

        int count = 0;

        // For each sum in the leftSums list, find the complementary sum in rightSums that sums up to x
        for (int leftSum : leftSums) {
            int complement = x - leftSum;
            count += countOccurrences(rightSums, complement);
        }

        return count;
    }

    // Helper method to generate all possible subset sums for a given array
    private List<Integer> generateSubsetSums(int[] nums) {
        List<Integer> sums = new ArrayList<>();
        int n = nums.length;

        // There are 2^n possible subsets
        for (int i = 0; i < (1 << n); i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                // Check if jth element is included in the subset
                if ((i & (1 << j)) != 0) {
                    sum += nums[j];
                }
            }
            sums.add(sum);
        }
        return sums;
    }

    // Helper method to count occurrences of a target value in a sorted list using binary search
    private int countOccurrences(List<Integer> list, int target) {
        // Find the first occurrence of the target using binary search
        int leftIndex = Collections.binarySearch(list, target);
        if (leftIndex < 0) {
            return 0; // Target not found
        }

        // Find the range of elements equal to target
        int count = 0;
        int index = leftIndex;

        // Count occurrences to the left
        while (index >= 0 && list.get(index) == target) {
            count++;
            index--;
        }

        // Count occurrences to the right
        index = leftIndex + 1;
        while (index < list.size() && list.get(index) == target) {
            count++;
            index++;
        }

        return count;
    }

    // Main method to test the function with different examples
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Test case 1
        int[] nums2 = {1, 2, 3, 4, 5};
        int x2 = 5;
        System.out.println("Number of subsets that sum to " + x2 + ": " + solution.countSubsets(nums2, x2));
        // Expected output: 3
        
        // Test case 2
        int[] nums1 = {2, 4, 6, 10};
        int x1 = 16;
        System.out.println("Number of subsets that sum to " + x1 + ": " + solution.countSubsets(nums1, x1));
        // Expected output: 2

        // Test case 3
        int[] nums3 = {7, -3, 2, 5, 1};
        int x3 = 9;
        System.out.println("Number of subsets that sum to " + x3 + ": " + solution.countSubsets(nums3, x3));
        // Expected output: 2
    }
}

Complexity Analysis

1. Generating Subset Sums:

   • For an array of length n, we split it into two halves. Each half contains n/2 elements.
   • For each half, the number of possible subsets is 2^(n/2). Generating all subset sums for each half requires O(2^(n/2) * (n/2)) time.

2. Sorting:

   • Sorting the rightSums list takes O(2^(n/2) * log(2^(n/2))) = O(2^(n/2) * (n/2)) time.

3. Binary Search:

   • For each sum in leftSums, we perform a binary search on rightSums. Since there are 2^(n/2) sums in leftSums and each binary search takes O(log(2^(n/2))) = O(n/2) time, this part requires O(2^(n/2)* (n/2)) time.

The overall time complexity of this approach is O(2^(n/2) * (n/2)).

Space Complexity:

The space complexity is dominated by the storage of subset sums, which takes 2^(n/2) space for each half. Thus, the space complexity is 2^(n/2).