Mastering Backtracking LeetCode Problems in Java

2025-08-10

Backtracking looks scary until you see the pattern. Most problems share the same bones. You build partial choices, explore deeper, and undo the last move when it does not lead to a solution. Think of it as controlled recursion with guardrails.

This guide gives you a clean Java template, then walks through the most common LeetCode patterns: subsets, permutations, combination search, board search, and placement puzzles. Each section includes code you can drop into your IDE.

---

The backtracking template

Key idea: choose → explore → unchoose. Use a list to hold the current path, a result list to collect answers, and pruning checks to avoid wasted work.

import java.util.*;

public class BacktrackTemplate {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    void backtrack(int[] nums, int start) {
        // record a snapshot when appropriate
        res.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            // optional pruning or skip duplicates here
            path.add(nums[i]);          // choose
            backtrack(nums, i + 1);     // explore
            path.remove(path.size() - 1); // unchoose
        }
    }
}

Rules of thumb:

• Record a copy, never the same list
• Pass indices or state that define what you can try next
• Prune as early as you can

---

1) Subsets

Return all subsets of a set. Order does not matter. No duplicates in input.

import java.util.*;

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

Complexity: O(n · 2^n) to generate and copy all subsets.

---

2) Subsets II with duplicates

Skip equal numbers at the same depth to avoid duplicate subsets.

import java.util.*;

public class SubsetsII {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // dedupe by level
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

---

3) Permutations

All orderings of distinct numbers.

import java.util.*;

public class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), res);
        return res;
    }
    void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        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;
        }
    }
}

Complexity: O(n · n!).

---

4) Permutations II with duplicates

Sort and skip equal numbers that would create duplicates at the same depth.

import java.util.*;

public class PermutationsII {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), res);
        return res;
    }
    void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // dedupe
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

---

5) Combination Sum

Pick numbers any number of times to reach a target sum. Order does not matter.

import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), res);
        return res;
    }
    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; // prune
            path.add(a[i]);
            backtrack(a, i, remain - a[i], path, res); // reuse allowed
            path.remove(path.size() - 1);
        }
    }
}

---

6) Combination Sum II

Use each number at most once. Skip duplicates.

import java.util.*;

public class CombinationSumII {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), res);
        return res;
    }
    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 (i > start && a[i] == a[i - 1]) continue;
            if (a[i] > remain) break;
            path.add(a[i]);
            backtrack(a, i + 1, remain - a[i], path, res);
            path.remove(path.size() - 1);
        }
    }
}

---

7) Generate Parentheses

Classic Catalan pattern. Only add a left if you have lefts remaining. Only add a right if it will not make the string invalid.

import java.util.*;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(n, 0, 0, new StringBuilder(), res);
        return res;
    }
    void backtrack(int n, int open, int close, StringBuilder sb, List<String> res) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append('(');
            backtrack(n, open + 1, close, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            backtrack(n, open, close + 1, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

8) Palindrome Partitioning

Split a string into palindromic pieces.

import java.util.*;

public class PalindromePartitioning {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), res);
        return res;
    }
    void backtrack(String s, int start, List<String> path, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPal(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }
    boolean isPal(String s, int l, int r) {
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

---

9) N Queens

Place n queens so no two attack each other. Track blocked columns and diagonals to prune fast.

import java.util.*;

public class NQueens {
    List<List<String>> res = new ArrayList<>();
    char[] rowTemplate;
    boolean[] col, diag1, diag2;

    public List<List<String>> solveNQueens(int n) {
        rowTemplate = new char[n];
        Arrays.fill(rowTemplate, '.');
        col = new boolean[n];
        diag1 = new boolean[2 * n]; // r + c
        diag2 = new boolean[2 * n]; // r - c + n
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) board[i] = rowTemplate.clone();
        backtrack(0, n, board);
        return res;
    }
    void backtrack(int r, int n, char[][] board) {
        if (r == n) {
            List<String> one = new ArrayList<>();
            for (char[] row : board) one.add(new String(row));
            res.add(one);
            return;
        }
        for (int c = 0; c < n; c++) {
            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;
        }
    }
}

---

10) Word Search

Check if a word exists in a grid by walking adjacent cells without revisiting a cell in the same path.

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] seen = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, word, 0, r, c, seen)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] b, String w, int i, int r, int c, boolean[][] seen) {
        if (i == w.length()) return true;
        if (r < 0 || c < 0 || r == b.length || c == b[0].length) return false;
        if (seen[r][c] || b[r][c] != w.charAt(i)) return false;

        seen[r][c] = true;
        boolean ok = dfs(b, w, i + 1, r + 1, c, seen)
                  || dfs(b, w, i + 1, r - 1, c, seen)
                  || dfs(b, w, i + 1, r, c + 1, seen)
                  || dfs(b, w, i + 1, r, c - 1, seen);
        seen[r][c] = false;
        return ok;
    }
}

---

When to prune

Pruning reduces the search tree size and often flips a time limit exceeded into an accepted solution.

• Sort candidates for sum problems and break when the running sum exceeds target
• Use boolean arrays for constant time safety checks in placement problems
• Skip duplicate values at the same recursion depth after sorting
• Check feasibility early rather than after building a full path

---

Talking through a backtracking solution in an interview

1. Define the state: what partial choice you track and what index or coordinates you are at
2. Define choices: which elements or moves are legal next
3. Add pruning rules and explain why they are safe
4. Show the choose → explore → unchoose flow in code
5. State complexity in terms of branching factor and depth, and where pruning improves it
6. Walk one example by hand and show where you backtrack

---

Quick practice list

• Letter Combinations of a Phone Number
• Restore IP Addresses
• Combination Sum variants
• Sudoku Solver
• N Queens
• Word Search and its variants
• Subsets and Permutations families
• Palindrome Partitioning

Cover these and most backtracking questions will feel familiar.

---

If you want a fast way to compare your idea to a clean solution while practicing, you can use a helper that overlays a step by step outline without interrupting your flow. When you are stuck and need a nudge, it can keep your momentum.

Try StealthCoder to capture the prompt and get a concise explanation you can study and explain back: https://stealthcoder.app