Backtracking in Java searches through possible choices. It chooses an option, recursively explores what follows, and then undoes that choice before trying another. This pattern is useful when you need combinations, permutations or valid arrangements rather than one direct calculation.
Recursion supplies the nested calls, but not every recursive method is backtracking. A factorial calculation follows one shrinking problem. A backtracking search branches into alternative candidate solutions and often rejects a branch as soon as it violates a constraint.
The choose, explore and undo pattern
Imagine packing a small display box from three sample cards. For each card, you can include it or leave it out. The partial box is your current state. The next card position describes what remains undecided. Once every card has been considered, that state is a complete candidate.
A base case must describe completion, failure or both. The recursive step must move toward that boundary. If a call retries the same position with unchanged state, there is no progress and the Java stack eventually overflows.
Mutable state needs particular care. Appending a card before a recursive call changes the shared list seen by that call. Removing it afterward restores the list for the next branch. This restoration is the backtracking step, not a cosmetic cleanup.
Local integer parameters behave differently from a shared list. Each call receives its own parameter value, while multiple calls can hold references to the same list object. Understanding that difference prevents many apparently mysterious duplicate results.
Duplicate values and the meaning of a choice
The permutation example treats positions as distinct. If the token array contains two identical letters, choosing the first A versus the second A can produce duplicate visible strings. A correct result definition must say whether identical values should yield repeated arrangements.
For unique permutations, one common approach sorts the values and skips an equal candidate when its preceding equal value has not been used in the current path. Another uses a small per-depth set to avoid choosing the same value twice at that position.
Subset problems have a related distinction between selecting positions and selecting unique value combinations. Do not delete duplicate results afterward without considering why the search generated them: avoiding duplicate branches can reduce work substantially.
Also distinguish combinations from permutations. Selecting Map and Badge is one combination regardless of their ordering. Placing them into first and second slots gives two permutations.
Complexity, early stopping and practical limits
Permutation generation has n! complete arrangements for n distinct values. Subset generation has 2ⁿ complete selections. Constructing or printing each result adds work proportional to its length. Small input limits are a necessary part of the specification.
The active recursive path is usually O(n) deep. Stored output can be much larger than that. Separate auxiliary search space from the space occupied by all retained answers when discussing complexity.
If you only need one solution, return a boolean from the recursive search and stop when a branch succeeds. If you need every solution, continue after recording each success. These goals require different control flow and different acceptance tests.
Backtracking explores candidates; dynamic programming reuses answers to repeated subproblems. They can sometimes be combined, but memoizing only a remaining sum is wrong when the available item position also changes the answer. Read dynamic programming next.
Recursion and Backtracking Summary
- Define completion and rejection cases before recursive branching.
- Make every recursive call progress toward a boundary.
- Undo shared mutable choices before exploring siblings.
- Copy results when retaining a changing partial list.
- Prune only when the input constraints justify the rejection.
Recursion and Backtracking Examples
Each example shows the code, the output it produces and what each part does.
Generating all subsets
Save this program as CardSubsetExample.java. Each card position creates a skip branch and an include branch.
The output order comes from exploring skip before include. Reversing those branches changes display order, not which subsets exist. With n distinct items, there are 2ⁿ subsets; an algorithm that prints them all cannot have polynomial total output time.
import java.util.ArrayList;
import java.util.List;
public class CardSubsetExample {
static void subsets(String[] cards, int index, List<String> chosen) {
if (index == cards.length) {
System.out.println(chosen);
return;
}
subsets(cards, index + 1, chosen);
chosen.add(cards[index]);
subsets(cards, index + 1, chosen);
chosen.remove(chosen.size() - 1);
}
public static void main(String[] args) {
subsets(new String[]{"Map", "Badge"}, 0, new ArrayList<>());
}
}[]
[Badge]
[Map]
[Map, Badge]Line-by-line explanation
- Lines 5 to 8Reaching the array's length means every inclusion decision has been made.
- Line 10The first branch leaves the current card out.
- Lines 11 to 13The second branch adds the card, explores it, and removes the same final entry.
- Line 17Two independently selectable cards produce four subsets, including the empty subset.
Generating permutations
A permutation chooses one unused item for each next position. This example keeps the partial sequence in an array.
The old value in result[depth] does not need clearing because the next valid branch overwrites that position before reading a complete result. The used array does need restoration: leaving a flag true would wrongly block that token in sibling branches.
public class TokenPermutationExample {
static void arrange(char[] tokens, boolean[] used,
char[] result, int depth) {
if (depth == tokens.length) {
System.out.println(new String(result));
return;
}
for (int i = 0; i < tokens.length; i++) {
if (used[i]) continue;
used[i] = true;
result[depth] = tokens[i];
arrange(tokens, used, result, depth + 1);
used[i] = false;
}
}
public static void main(String[] args) {
char[] tokens = {'A', 'B', 'C'};
arrange(tokens, new boolean[tokens.length],
new char[tokens.length], 0);
}
}ABC
ACB
BAC
BCA
CAB
CBALine-by-line explanation
- Lines 4 to 6A full-length result is printed as a complete arrangement.
- Lines 8 to 10The loop considers each still-unused token and marks the chosen one.
- Lines 11 to 13The recursive call fills the next position; clearing used restores availability afterward.
- Lines 18 to 20Three distinct tokens produce six arrangements.
Pruning impossible sum branches
These positive package sizes can each be selected at most once. The search prints selections totaling seven.
The remaining < 0 pruning rule relies on positive sizes. If negative values were allowed later, an overshoot could still be repaired. Pruning must follow the problem's constraints rather than a copied condition from another search.
import java.util.ArrayList;
import java.util.List;
public class PackageChoiceExample {
static void search(int[] sizes, int index, int remaining,
List<Integer> chosen) {
if (remaining == 0) {
System.out.println(chosen);
return;
}
if (index == sizes.length || remaining < 0) return;
chosen.add(sizes[index]);
search(sizes, index + 1, remaining - sizes[index], chosen);
chosen.remove(chosen.size() - 1);
search(sizes, index + 1, remaining, chosen);
}
public static void main(String[] args) {
search(new int[]{2, 5, 7}, 0, 7, new ArrayList<>());
}
}[2, 5]
[7]Line-by-line explanation
- Lines 7 to 9A remaining target of zero means the selected packages exactly meet the target.
- Line 11Exhausted input or an overshot positive-size target ends an unsuccessful branch.
- Lines 12 to 15The include branch spends the current size, undoes its list change, then tries exclusion.
- Line 19The two valid selections are two plus five and seven alone.
Recursion and Backtracking FAQ
Is every DFS algorithm backtracking?
DFS explores deeply, but the term backtracking usually emphasizes building and undoing candidate choices. A graph DFS may simply mark each vertex once.
Should every branch copy its state?
Not necessarily. Shared state with precise restoration is efficient; copies are often easier to reason about. Choose deliberately and test sibling independence.
Is backtracking the same as brute force?
It's a systematic brute force with an important improvement: it abandons a partial candidate as soon as it can't lead to a valid answer. That pruning can cut away huge parts of the search, although the worst case usually remains exponential.
Why is backtracking slow for large inputs?
The number of candidates grows explosively: 2ⁿ subsets and n! permutations. Twenty items already have over a million subsets, and twelve items have almost half a billion orderings. Strong pruning, good choice ordering or a different algorithm, such as dynamic programming, is needed beyond small inputs.
Which classic problems use backtracking?
Generating subsets, permutations and combinations, the N-Queens puzzle, solving Sudoku, finding words in a letter grid and choosing items that hit an exact total. They all share the same shape: choose, explore, and undo the choice.
Recursion and Backtracking Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
Why does the subset example remove the final chosen card after its recursive call?
How many permutations does the distinct array A, B, C have?
Recursion and Backtracking Quiz
2 questions to check what you learned.
Which operation safely stores an independent list of current selections?
- results.add(new ArrayList<>(chosen))
- results.add(chosen) followed by modifying chosen
- chosen.clear() before storing its contents
When is remaining < 0 a valid rejection rule for the package example?
- When all remaining package sizes are positive
- Even when later packages may have negative sizes
- Only when the list is already sorted alphabetically