Subset Sum

Lab C++ Advanced 30 points

Read n (≤ 15) positive integers and a target. Print how many subsets sum exactly to the target, by recursion that includes or skips each number.

Input

n, the numbers, then the target.

Output

One integer.

Example

Input

5
1 2 3 4 5
5

Output

Sample input available Sample output available

Editor

C++

Hints

Each number is either in the subset or not - two recursive calls.

Solution explanation

With all numbers positive, a negative remainder means the branch can stop early.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int countSubsets(const vector<int> &v, int i, int remaining) {
    if (remaining == 0) return 1;
    if (i == (int) v.size() || remaining < 0) return 0;
    return countSubsets(v, i + 1, remaining - v[i]) + countSubsets(v, i + 1, remaining);
}

int main() {
    int n, target;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    cin >> target;
    cout << countSubsets(v, 0, target) << "\n";
    return 0;
}

Output

Answer