All Subsets

Lab Java Advanced 30 points

Read n distinct letters (one word). Print every subset in the order produced by "include the letter, then exclude it" recursion, one per line; print the empty subset as {}.

Input

One word of up to 5 distinct letters.

Output

2ⁿ lines.

Example

Input

abc

Output

abc
ab
ac
a
bc
b
c
{}

Sample input available Sample output available

Editor

Java

Hints

For each letter there are two branches: take it or leave it.

Solution explanation

This include/exclude pattern is the basis of backtracking algorithms.

Show solution

import java.util.Scanner;

public class Main {
    static void subsets(String letters, int i, String current) {
        if (i == letters.length()) {
            System.out.println(current.isEmpty() ? "{}" : current);
            return;
        }
        subsets(letters, i + 1, current + letters.charAt(i));
        subsets(letters, i + 1, current);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        subsets(sc.next(), 0, "");
    }
}

Output

Answer