Backtracking LeetCode Problems in Java: Patterns

Backtracking LeetCode problems in Java all follow one loop: choose an option, recurse deeper, then undo the choice. Once you memorize that skeleton and learn three small variations (start index, used array, remaining target), most subset, permutation, combination, and placement problems become small edits of the same code.

TL;DR

• Every backtracking solution is choose → explore → unchoose.
• Always add new ArrayList<>(path) to the results, never path itself.
• Use a start index for subsets and combinations, a used[] array for permutations.
• Sort first, then skip nums[i] == nums[i-1] to handle duplicates.
• Prune early (for example, break when a sorted candidate exceeds the remaining target).
• Subsets cost O(n · 2^n); permutations cost O(n · n!).
• Practice narrating the pattern out loud, since interviewers grade your reasoning as much as your code.

What Is the Backtracking Template in Java?

The template is a recursive method that carries the current partial answer (path), a position or state, and a shared results list. At each step you try every legal option, recurse, and remove the option you just added.

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));            // snapshot
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                     // choose
        backtrack(nums, i + 1, path, res);     // explore
        path.remove(path.size() - 1);          // unchoose
    }
}

Three questions decide how you adapt it:

1. When is a path complete? Every node (subsets), full length (permutations), or remaining target equals zero (combination sum).
2. What can I pick next? Anything after index i, anything unused, or anything from i onward if reuse is allowed.
3. What can I skip? Duplicates, overshooting sums, invalid brackets, attacked squares.

A reliable rule: the pattern is determined by whether order matters and whether elements can repeat.

Problem type	Order matters?	Reuse allowed?	Next-choice rule
Subsets	No	No	Loop from start, recurse i + 1
Permutations	Yes	No	Loop from 0, skip used[i]
Combination Sum	No	Yes	Loop from start, recurse i
Combination Sum II	No	No	Recurse i + 1, skip duplicates

How Do You Solve Subsets and Subsets II?

Record a snapshot at every call, then loop from start and recurse with i + 1. This generates 2^n subsets, and copying each one gives O(n · 2^n) total work.

For input with duplicates (Subsets II), sort the array and add one guard inside the loop:

if (i > start && nums[i] == nums[i - 1]) continue;

The condition i > start is the key detail. It allows a duplicate to be used deeper in the same path but blocks it from starting a second branch at the same level. Candidates often write i > 0 and get missing answers.

How Do You Generate Permutations Without Repeats?

Use a boolean[] used array and loop from index 0 each time. A path is complete when its size equals nums.length.

for (int i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true;
    path.add(nums[i]);
    backtrack(nums, used, path, res);
    path.remove(path.size() - 1);
    used[i] = false;
}

For Permutations II, sort first and add if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;. This forces equal values to be consumed left to right, which removes duplicate orderings. Note that you must undo two things here: the list and the flag.

How Do You Handle Combination Sum Problems?

Sort the candidates, loop from start, and break as soon as a candidate exceeds the remaining target. Sorting is what makes that break valid, and it is the cheapest pruning you can add.

• Combination Sum (reuse allowed): recurse with i, since the same number may be picked again.
• Combination Sum II (single use): recurse with i + 1 and skip i > start duplicates.

void backtrack(int[] a, int start, int remain, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < a.length; i++) {
        if (a[i] > remain) break;
        path.add(a[i]);
        backtrack(a, i, remain - a[i], path, res);
        path.remove(path.size() - 1);
    }
}

If an interviewer asks about complexity, say it is exponential in the worst case, bounded by the target divided by the smallest candidate for recursion depth. For a refresher on explaining that cleanly, see this guide on explaining Big O complexity in coding interviews.

How Do Parentheses and Partitioning Problems Fit the Pattern?

Both use constraints instead of a loop over a flat array.

Generate Parentheses: track open and close counts. Add ( only when open < n, and add ) only when close < open. Those two checks guarantee every string is valid, so no validation is needed at the end. Use a StringBuilder and deleteCharAt(sb.length() - 1) to undo.

Palindrome Partitioning: at each start, try every end, and only recurse when s[start..end] is a palindrome. Complete the path when start == s.length(). A common optimization is precomputing a palindrome table with dynamic programming, which links this topic to dynamic programming interview questions.

How Do You Solve N-Queens Efficiently?

Place one queen per row and track attacked columns and diagonals in three boolean arrays. For a square at row r and column c, the diagonals are identified by r + c and r - c + n, so each conflict check is O(1).

if (col[c] || diag1[r + c] || diag2[r - c + n]) continue;
col[c] = diag1[r + c] = diag2[r - c + n] = true;
board[r][c] = 'Q';
backtrack(r + 1, n, board);
board[r][c] = '.';
col[c] = diag1[r + c] = diag2[r - c + n] = false;

Word Search follows the same idea on a grid: mark a cell visited, explore four neighbors, and restore the cell on return.

What Mistakes Cost Candidates the Most Points?

• Adding path instead of a copy. Every stored answer ends up empty.
• Forgetting to undo state. Remember used[i] = false and board resets.
• Using the wrong dedupe condition. i > start for combinations and subsets; !used[i-1] for permutations.
• Skipping the sort. Duplicate-skipping and break pruning both depend on it.
• Not stating complexity. Say O(n · 2^n) or O(n · n!) before you are asked.

How Should You Practice Backtracking for Interviews?

Rewrite the template from memory until you can do it in under five minutes, then solve one problem from each row of the table above. Fold this into a structured schedule such as an 8-week coding interview roadmap so recursion practice is spaced rather than crammed.

During live rounds, the hard part is often keeping your thinking organized under pressure: choosing the right pattern, spotting the dedupe rule, and explaining it aloud. CloakAI is an invisible AI interview assistant that can help you reason through pattern selection in real time, and it works best when you already understand the template above. Use it to sharpen your approach during practice sessions, and always follow the rules of any assessment you take.

FAQ

Q: What is the difference between backtracking and recursion? A: Recursion is a technique where a function calls itself; backtracking is recursion that builds a partial solution and undoes the last choice when it fails or after recording it.

Q: Why do I need to copy the path list before adding it to results? A: Java lists are references, so adding path directly stores the same object that later gets modified. Use new ArrayList<>(path) to save a snapshot.

Q: What is the time complexity of subsets and permutations? A: Subsets run in O(n · 2^n) and permutations in O(n · n!), where the factor of n comes from copying each result.

Q: How do I avoid duplicate results in backtracking? A: Sort the input, then skip an element equal to its predecessor at the same recursion level. Use i > start for subsets and combinations, and !used[i-1] for permutations.

Q: Which backtracking problems should I practice first? A: Start with Subsets, Permutations, Combination Sum, Generate Parentheses, and N-Queens, because together they cover the main variations of the template.

Conclusion

Backtracking is one template with a few knobs: when to record, what to try next, and what to skip. Master those three decisions, practice the dedupe conditions, and state your complexity clearly. Do that, and most backtracking LeetCode problems in Java become a quick adaptation rather than a fresh puzzle.