Challenge: Make the Target

Lab C++ Intermediate 20 points

Given distinct positive numbers (numbers may be reused) and a target, print every combination that adds up to the target in non-decreasing order, joined with +, in the order backtracking finds them with sorted numbers. Then print Ways: <count>.

Input

Line 1: n target (target ≤ 40). Line 2: n distinct positive numbers.

Output

The combinations, then the count.

Example

Input

4 7
2 3 6 7

Output

2+2+3
7
Ways: 2

Sample input available Sample output available

Editor

C++

Hints

Sort first.

Recurse with i (not i + 1) so a number can repeat.

Break when nums[i] > left.

Solution explanation

Starting each loop at start keeps combinations in order, so none appears twice.

Show solution

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

vector<int> nums, cur;
int ways = 0;

void explore(int start, int left) {
    if (left == 0) {
        for (size_t i = 0; i < cur.size(); i++) cout << cur[i] << (i + 1 < cur.size() ? "+" : "\n");
        ways++;
        return;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        if (nums[i] > left) break;
        cur.push_back(nums[i]);
        explore(i, left - nums[i]);
        cur.pop_back();
    }
}

int main() {
    int n, target;
    cin >> n >> target;
    nums.resize(n);
    for (int& x : nums) cin >> x;
    sort(nums.begin(), nums.end());
    explore(0, target);
    cout << "Ways: " << ways << endl;
    return 0;
}

Output

Answer