Variations

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Variations {
    public static void main(String[] args) throws IOException {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(reader);

        int length = Integer.parseInt(bf.readLine());
        char[] symbols = bf.readLine().replaceAll(" ", "").toCharArray();

        List<String> validCombinations = new ArrayList<>();

        getAllValidCombinations("", length, symbols, 0, validCombinations);

        Collections.sort(validCombinations);
        for (int i = 0; i < validCombinations.size(); i++) {
            System.out.println(validCombinations.get(i));
        }
    }

    private static void getAllValidCombinations(String combination,
                                                int length,
                                                char[] symbols,
                                                int index,
                                                List<String> validCombinations) {
        if (index == length) {
            validCombinations.add(combination);
            return;
        }

        for (int i = 0; i <= 1; i++) {
            String output = combination + symbols[i];
            getAllValidCombinations(output, length, symbols, index + 1, validCombinations);
        }

    }
}