Count Subset With Target Sum II – Meet in the Middle Java Solution

Introduction

The Count Subset With Target Sum II problem asks us to count the number of subsets whose sum equals a given target k.

At first glance, this looks like a classic subset-sum problem that can be solved using recursion or dynamic programming. However, there is an important constraint:

1 ≤ n ≤ 40

Additionally:

-10^7 ≤ arr[i], k ≤ 10^7

Because the array can contain negative numbers and the size can reach 40, traditional DP approaches become impractical.

This is where the powerful Meet in the Middle (MITM) technique comes into play.

Problem Statement

Given:

arr[]

and an integer:

Find the number of subsets whose sum equals:

Return the count.

Example 1

Input

arr = [1, 3, 2]
k = 3

Valid Subsets

[3]
[1,2]

Output

Example 2

Input

arr = [4,2,3,1,2]
k = 4

Valid Subsets

[4]
[2,2]
[3,1]

Output

Example 3

Input

arr = [10,20,30]
k = 25

No subset sums to 25.

Output

Why Brute Force Fails

A subset can either:

Include an element
Exclude an element

For n elements:

Total Subsets = 2^n

For:

n = 40

we get:

2^40 ≈ 1 trillion

Checking all subsets is impossible.

Complexity

O(2^n)

This is too slow.

Key Observation

The constraint:

n ≤ 40

suggests splitting the array into two halves.

Example:

[4,2,3,1,2]

Split into:

Left  = [4,2]
Right = [3,1,2]

Instead of generating:

2^40

subsets, generate:

2^20 + 2^20

subsets.

This is dramatically smaller.

Meet in the Middle Concept

Divide the array into two halves.

Left Half
Right Half

Generate all subset sums for both halves.

Example:

Left = [1,3]

Subset sums:

For:

Right = [2]

Subset sums:

0
2

Now find combinations where:

leftSum + rightSum = k

instead of checking all subsets directly.

Generating Subset Sums

Suppose:

Left = [1,3]

Possible subsets:

{}
{1}
{3}
{1,3}

Sums:

Store them in a list.

Matching Target Sum

For every sum:

from the left half, we need:

k - x

from the right half.

If that value appears multiple times, all occurrences contribute to the answer.

Efficient Counting

Store frequencies of right-half subset sums.

Example:

Right Sums

Frequency Map

0 → 1
2 → 2
4 → 1

Now for each left sum:

required = k - leftSum

Add:

frequency(required)

to the answer.

Algorithm

Step 1

Split the array into:

Left Half
Right Half

Step 2

Generate all subset sums of the left half.

Step 3

Generate all subset sums of the right half.

Step 4

Store right-half sums in a HashMap.

Map<Long,Integer>

to count frequencies.

Step 5

For every left sum:

required = k - leftSum

If present in the map:

answer += frequency(required)

Step 6

Return the answer.

Dry Run

Input

arr = [1,3,2]
k = 3

Split

Left  = [1]
Right = [3,2]

Left Sums

Subsets:

{}
{1}

Sums:

0
1

Right Sums

Subsets:

{}
{3}
{2}
{3,2}

Sums:

Frequency Map

Matching

For:

leftSum = 0

Need:

Found once.

Answer:

For:

leftSum = 1

Need:

Found once.

Answer:

Final Answer

Java Solution

class Solution {

    private void generateSums(int[] arr,
                              int start,
                              int end,
                              long sum,
                              ArrayList<Long> sums) {

        if (start == end) {
            sums.add(sum);
            return;
        }

        generateSums(arr, start + 1, end,
                     sum, sums);

        generateSums(arr, start + 1, end,
                     sum + arr[start], sums);
    }

    public int countSubset(int[] arr, int k) {

        int n = arr.length;

        int mid = n / 2;

        ArrayList<Long> leftSums = new ArrayList<>();
        ArrayList<Long> rightSums = new ArrayList<>();

        generateSums(arr, 0, mid, 0, leftSums);

        generateSums(arr, mid, n, 0, rightSums);

        HashMap<Long, Integer> freq = new HashMap<>();

        for (long sum : rightSums) {
            freq.put(sum,
                freq.getOrDefault(sum, 0) + 1);
        }

        long answer = 0;

        for (long left : leftSums) {

            long required = (long) k - left;

            answer += freq.getOrDefault(required, 0);
        }

        return (int) answer;
    }
}

Why Use Long?

Although:

arr[i] ≤ 10^7

we may sum up to:

40 × 10^7

which can exceed integer limits.

Therefore:

long

is safer for subset sums.

Complexity Analysis

Let:

n = 40

Split:

20 + 20

Generating Subset Sums

For each half:

O(2^(n/2))

Building Frequency Map

O(2^(n/2))

Matching

O(2^(n/2))

Total Time Complexity

O(2^(n/2))

which matches the expected complexity.

Space Complexity

Store subset sums:

O(2^(n/2))

For:

n = 40

this becomes:

O(2^20)

which is manageable.

Why Meet in the Middle Works

Instead of exploring:

2^40

subsets directly, we explore:

2^20 + 2^20

subsets and combine the results efficiently.

This reduces the search space from:

1,099,511,627,776

to approximately:

2,097,152

operations.

That is the key idea behind Meet in the Middle.

Edge Cases

Empty Subset Equals Target

arr = [1,2]
k = 0

Valid subset:

{}

Answer:

Negative Numbers

arr = [-1,1]
k = 0

Subsets:

{}
[-1,1]

Answer:

The MITM approach naturally handles negative numbers.

No Valid Subset

arr = [10,20,30]
k = 5

Answer:

Conclusion

The Count Subset With Target Sum II problem is a classic application of the Meet in the Middle technique.

The key insight is:

Split the array into two halves, generate all subset sums separately, and efficiently combine them using a frequency map.

This transforms an impossible:

O(2^n)

solution into:

O(2^(n/2))

which is exactly what the constraints require.

Final Complexity

Time Complexity  : O(2^(n/2))
Space Complexity : O(2^(n/2))

making it ideal for arrays of size up to 40.