Challenge: Spend the Gift Card Exactly

Lab Java Intermediate 20 points

You have a gift card and a list of item prices (all different, given in increasing order). Print every set of items whose prices add up exactly to the card value – one set per line, prices in increasing order – then ways: k. List the sets in the order a take-it-first backtracking search finds them. Prune: stop as soon as the total goes over.

Input

Line 1: n card (n ≤ 15). Line 2: n increasing prices.

Output

Each matching set on its own line, then ways: k.

Example

Input

6 10
1 2 3 4 6 7

Output

Sample input available Sample output available

Editor

Java

Hints

pick(i, total, chosen): try each item j from i onwards as the next one in the set.

Prices are sorted, so once total + price[j] is too big, every later item is too big as well – break.

Solution explanation

Without pruning this explores all 2ⁿ subsets. Because the prices are sorted, one break cuts off whole branches at once.

Show solution

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int[] price;
    static int card, ways = 0;
    static StringBuilder out = new StringBuilder();

    static void pick(int i, int total, ArrayList<Integer> chosen) {
        if (total == card) {
            for (int k = 0; k < chosen.size(); k++) out.append(k > 0 ? " " : "").append(chosen.get(k));
            out.append('\n');
            ways++;
            return;
        }
        for (int j = i; j < price.length; j++) {
            if (total + price[j] > card) break;      // prune: prices only get bigger
            chosen.add(price[j]);
            pick(j + 1, total + price[j], chosen);
            chosen.remove(chosen.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        card = sc.nextInt();
        price = new int[n];
        for (int i = 0; i < n; i++) price[i] = sc.nextInt();
        pick(0, 0, new ArrayList<Integer>());
        out.append("ways: ").append(ways);
        System.out.println(out);
    }
}

Output

Answer