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:
k
Find the number of subsets whose sum equals:
k
Return the count.
Example 1
Input
arr = [1, 3, 2]
k = 3
Valid Subsets
[3]
[1,2]
Output
2
Example 2
Input
arr = [4,2,3,1,2]
k = 4
Valid Subsets
[4]
[2,2]
[3,1]
Output
3
Example 3
Input
arr = [10,20,30]
k = 25
No subset sums to 25.
Output
0
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:
0
1
3
4
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:
0
1
3
4
Store them in a list.
Matching Target Sum
For every sum:
x
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
0
2
2
4
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:
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:
0
3
2
5
Frequency Map
0 → 1
2 → 1
3 → 1
5 → 1
Matching
For:
leftSum = 0
Need:
3
Found once.
Answer:
1
For:
leftSum = 1
Need:
2
Found once.
Answer:
2
Final Answer
2
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:
1
Negative Numbers
arr = [-1,1]
k = 0
Subsets:
{}
[-1,1]
Answer:
2
The MITM approach naturally handles negative numbers.
No Valid Subset
arr = [10,20,30]
k = 5
Answer:
0
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.