Count the subsets of n positive numbers whose sum is exactly S. The empty subset counts when S is 0. Numbers in different positions are different items, even when they are equal.
What to build
A recursive program that counts the subsets with a given sum.
Requirements
- For each item, try leaving it out and putting it in.
- Count one way when every item is decided and the sum is exactly
S. - Print the total number of subsets.
Input
The first line has n and S (1 ≤ n ≤ 12, 0 ≤ S ≤ 1000). The second line has the n numbers, each from 1 to 100.
Output
The number of subsets.
Constraints
1 ≤ n ≤ 12, 0 ≤ S ≤ 1000, and each number is from 1 to 100.
Example
Input:
4 5
1 2 3 4
Output:
2
Why it works
Each item is in or out, so the recursion visits all 2ⁿ subsets, at most 4096 here, and counts those with the right sum.
Examples
4 5 1 2 3 4
2
3 0 1 2 3
1
Hints
Hint 1
Write count(i, sum): the number of ways to choose from items i .. n-1 so the total becomes S, when the chosen ones so far add up to sum.
Hint 2
When i == n, return 1 if sum == S, else 0.
Hint 3
Otherwise return count(i + 1, sum) + count(i + 1, sum + a[i]): leave item i out, or put it in.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int n, S;
int a[12];
int count(int i, int sum) {
if (i == n) return sum == S ? 1 : 0;
return count(i + 1, sum) + count(i + 1, sum + a[i]);
}
int main(void) {
scanf("%d %d", &n, &S);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d\n", count(0, 0));
return 0;
}