All Permutations of a String

/*
 * Problem : Print all permutations.
 * Input   : One word.
 * Output  : All permutations.
 * Approach: Backtracking.
 * Time    : O(n * n!)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // This method builds all permutations. "current" is the part we have built, "used" marks the letters in it.
        static void build(char[] letters, boolean[] used, StringBuilder current, java.util.List<String> result) {
            // Step 1: If current has all letters, it is one complete permutation.
            if (current.length() == letters.length) {
                result.add(current.toString());
                return;
            }

            // Step 2: Try every letter that is not used yet, in sorted order.
            for (int i = 0; i < letters.length; i++) {
                if (!used[i]) {
                    // Step 3: Choose the letter, solve the rest, then undo the choice (backtracking).
                    used[i] = true;
                    current.append(letters[i]);
                    build(letters, used, current, result);
                    current.deleteCharAt(current.length() - 1);
                    used[i] = false;
                }
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String s) {
        // Step 4: Sort the letters first, so the results come in alphabetical order.
        char[] letters = s.toCharArray();
        java.util.Arrays.sort(letters);
        java.util.List<String> result = new java.util.ArrayList<>();
        build(letters, new boolean[letters.length], new StringBuilder(), result);
        return result.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(String.join("\n", solve(s)));
    }
}