Challenge: Every Subset

Lab C++ Intermediate 20 points

Print every subset of n distinct letters with backtracking: at each letter, explore taking it first, then skipping it. Print each subset's letters joined together, and the empty subset as {}.

Input

Line 1: n (n ≤ 10). Line 2: n distinct letters separated by spaces.

Output

2ⁿ lines.

Example

Input

3
a b c

Output

abc
ab
ac
a
bc
b
c
{}

Sample input available Sample output available

Editor

C++

Hints

explore(i) decides about items[i].

push_back, explore(i + 1), pop_back, explore(i + 1).

Solution explanation

Each letter is in or out: 2ⁿ subsets.

Show solution

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

vector<char> items;
string cur;

void explore(int i) {
    if (i == (int)items.size()) {
        cout << (cur.empty() ? "{}" : cur) << endl;
        return;
    }
    cur.push_back(items[i]);
    explore(i + 1);
    cur.pop_back();
    explore(i + 1);
}

int main() {
    int n;
    cin >> n;
    items.resize(n);
    for (char& c : items) cin >> c;
    explore(0);
    return 0;
}

Output

Answer