Backtracking: Choose, Explore, Undo

Trying every path in a maze

At each junction pick a path; if you hit a dead end, walk back to the last junction and try another. That's backtracking. In code it's always the same three steps inside a recursive method:

1. Choose – add an option to the current answer.
2. Explore – recurse to make the next choice.
3. Un-choose – remove the option again, so the next option starts clean.

Every arrangement (permutation)

public class Main {
    static void arrange(String letters, StringBuilder current, boolean[] used) {
        if (current.length() == letters.length()) {      // a full arrangement
            System.out.println(current);
            return;
        }
        for (int i = 0; i < letters.length(); i++) {
            if (used[i]) continue;
            used[i] = true;                               // choose
            current.append(letters.charAt(i));
            arrange(letters, current, used);              // explore
            current.deleteCharAt(current.length() - 1);   // un-choose
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        arrange("ABC", new StringBuilder(), new boolean[3]);
    }
}

Output

ABC
ACB
BAC
BCA
CAB
CBA

Every subset

For each item there are two choices: take it or leave it. That gives 2ⁿ subsets:

import java.util.ArrayList;

public class Main {
    static String[] toppings = {"cheese", "olives", "corn"};

    static void subsets(int i, ArrayList<String> chosen) {
        if (i == toppings.length) {
            System.out.println(chosen);
            return;
        }
        chosen.add(toppings[i]);                 // take it
        subsets(i + 1, chosen);
        chosen.remove(chosen.size() - 1);        // undo
        subsets(i + 1, chosen);                  // leave it
    }

    public static void main(String[] args) {
        subsets(0, new ArrayList<String>());
    }
}

Output

[cheese, olives, corn]
[cheese, olives]
[cheese, corn]
[cheese]
[olives, corn]
[olives]
[corn]
[]

Common mistake: Forgetting the un-choose step. The next branch then starts with leftovers from the previous one and the answers come out wrong.