Java solutions for the backtracking round — subsets (with and without duplicates), permutations, combination sum, N-Queens, Sudoku solver, word search, palindrome partitioning, generating parentheses, rat in a maze, phone-number letter combinations, expression add operators, restoring IP addresses, the k-th permutation, Gray code, all paths in a DAG, splitting a string into a Fibonacci sequence, validating balanced parentheses, word break, and removing invalid parentheses.
Published September 25, 2026
Backtracking follows one template: choose → explore → un-choose, with pruning to cut dead branches early.
void backtrack(State s) {
if (isSolution(s)) { record(s); return; }
for (Choice c : choices(s)) {
if (!valid(s, c)) continue; // prune
apply(s, c);
backtrack(s);
undo(s, c); // restore state
}
}
For each problem, state what a choice is, when to stop, how to prune, and the complexity (usually exponential: be explicit, for example O(2ⁿ·n) for subsets).
Short answer:
i ≥ start. That gives 2ⁿ subsets: O(n·2ⁿ).a[i] == a[i-1] when i > start (the same value at the same tree level produces duplicate subsets). (Subsets)void subsets(int[] a, int start, Deque<Integer> path, List<List<Integer>> out) { // a sorted for the dup variant
out.add(new ArrayList<>(path));
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue; // only needed with duplicates
path.addLast(a[i]); subsets(a, i + 1, path, out); path.removeLast();
}
}
Short answer: Build the permutation position by position, with a used[] array (or swap in place). O(n·n!). With duplicates: sort, and skip a[i]==a[i-1] && !used[i-1]. (Permutations)
void permute(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out) {
if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
for (int i = 0; i < a.length; i++) {
if (used[i]) continue;
used[i] = true; path.add(a[i]);
permute(a, used, path, out);
path.remove(path.size() - 1); used[i] = false;
}
}
Short answer: Candidates can be reused, so recurse with the same index i. Sort, and break when a candidate exceeds the remaining target (pruning). For "each number used once" (Combination Sum II), recurse with i+1, and skip duplicates at the same level. (Combination Sum)
void combine(int[] c, int start, int remain, List<Integer> path, List<List<Integer>> out) {
if (remain == 0) { out.add(new ArrayList<>(path)); return; }
for (int i = start; i < c.length && c[i] <= remain; i++) { // c sorted
path.add(c[i]); combine(c, i, remain - c[i], path, out); path.remove(path.size() - 1);
}
}
Short answer: Place one queen per row. Track the used columns, diagonals (r - c + n - 1) and anti-diagonals (r + c) in boolean arrays, so each safety check is O(1). The complexity is about O(n!). (Bitmasks make it faster.) (N-Queens)
int totalNQueens(int n) { return place(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]); }
int place(int r, int n, boolean[] col, boolean[] d1, boolean[] d2) {
if (r == n) return 1;
int count = 0;
for (int c = 0; c < n; c++) {
if (col[c] || d1[r - c + n] || d2[r + c]) continue;
col[c] = d1[r - c + n] = d2[r + c] = true;
count += place(r + 1, n, col, d1, d2);
col[c] = d1[r - c + n] = d2[r + c] = false;
}
return count;
}
Short answer: Keep bitmasks, or boolean arrays, for the digits used in each row, column and 3×3 box. Find the next empty cell, try the digits 1–9 that are allowed, recurse, and undo on failure. A big speed-up: pick the empty cell with the fewest candidates first (MRV heuristic).
boolean solve(char[][] b) {
for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) {
if (b[r][c] != '.') continue;
for (char d = '1'; d <= '9'; d++) {
if (canPlace(b, r, c, d)) { b[r][c] = d; if (solve(b)) return true; b[r][c] = '.'; }
}
return false; // no digit fits: backtrack
}
return true; // no empty cell left
}
boolean canPlace(char[][] b, int r, int c, char d) {
for (int i = 0; i < 9; i++)
if (b[r][i] == d || b[i][c] == d || b[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == d) return false;
return true;
}
Short answer: Start a DFS from each cell that matches the first letter. Mark the cell as visited (temporarily overwrite it with '#'), explore the 4 neighbours for the next letter, then restore it. O(m·n·4^L) for word length L. For many words (Word Search II), build a trie of the words, and DFS once.
boolean exist(char[][] g, String w) {
for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++)
if (dfs(g, w, 0, r, c)) return true;
return false;
}
boolean dfs(char[][] g, String w, int k, int r, int c) {
if (k == w.length()) return true;
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != w.charAt(k)) return false;
char t = g[r][c]; g[r][c] = '#';
boolean found = dfs(g, w, k + 1, r + 1, c) || dfs(g, w, k + 1, r - 1, c)
|| dfs(g, w, k + 1, r, c + 1) || dfs(g, w, k + 1, r, c - 1);
g[r][c] = t;
return found;
}
Short answer: From start, try every end i such that s[start..i] is a palindrome, then recurse from i+1. Precompute isPal[i][j] with DP, so each check is O(1). The worst case is O(n·2ⁿ) (for example, "aaaa…").
void partition(String s, int start, boolean[][] pal, List<String> path, List<List<String>> out) {
if (start == s.length()) { out.add(new ArrayList<>(path)); return; }
for (int i = start; i < s.length(); i++) if (pal[start][i]) {
path.add(s.substring(start, i + 1)); partition(s, i + 1, pal, path, out); path.remove(path.size() - 1);
}
}
// pal[i][j] = s[i]==s[j] && (j - i < 2 || pal[i+1][j-1]), filled for i from n-1 down to 0
Short answer: Add ( while open < n; add ) while close < open. That produces only valid strings (no filtering needed). The count is the n-th Catalan number, so it's O(4ⁿ/√n).
void gen(int open, int close, int n, StringBuilder sb, List<String> out) {
if (sb.length() == 2 * n) { out.add(sb.toString()); return; }
if (open < n) { sb.append('('); gen(open + 1, close, n, sb, out); sb.deleteCharAt(sb.length() - 1); }
if (close < open) { sb.append(')'); gen(open, close + 1, n, sb, out); sb.deleteCharAt(sb.length() - 1); }
}
Short answer: DFS from (0,0) to (n-1,n-1) through open cells, trying the directions in a fixed order (D, L, R, U, for lexicographic output). Mark cells visited on the current path, and unmark them on return. Record the path string when you reach the target. The worst case is exponential. For just the shortest path, use BFS instead.
void solve(int[][] m, int r, int c, boolean[][] vis, StringBuilder path, List<String> out) {
int n = m.length;
if (r == n - 1 && c == n - 1) { out.add(path.toString()); return; }
int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; char[] name = {'D', 'L', 'R', 'U'};
vis[r][c] = true;
for (int k = 0; k < 4; k++) {
int nr = r + dirs[k][0], nc = c + dirs[k][1];
if (nr >= 0 && nc >= 0 && nr < n && nc < n && m[nr][nc] == 1 && !vis[nr][nc]) {
path.append(name[k]); solve(m, nr, nc, vis, path, out); path.deleteCharAt(path.length() - 1);
}
}
vis[r][c] = false;
}
// call only if m[0][0] == 1
Short answer: Map each digit to its letters, and do a DFS over the positions, appending each letter. O(4ⁿ·n). Return an empty list for empty input.
static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void letters(String d, int i, StringBuilder sb, List<String> out) {
if (i == d.length()) { if (sb.length() > 0) out.add(sb.toString()); return; }
for (char ch : KEYS[d.charAt(i) - '0'].toCharArray()) {
sb.append(ch); letters(d, i + 1, sb, out); sb.deleteCharAt(sb.length() - 1);
}
}
Short answer: Try each number split (no leading zeros), and each operator + - *, tracking the current value and the last operand. For *: value - last + last * cur (it undoes the previous term, respecting precedence). Use long for overflow. O(4ⁿ).
void ops(String num, int target, int pos, long value, long last, StringBuilder expr, List<String> out) {
if (pos == num.length()) { if (value == target) out.add(expr.toString()); return; }
for (int i = pos; i < num.length(); i++) {
if (i > pos && num.charAt(pos) == '0') break; // no leading zeros
long cur = Long.parseLong(num.substring(pos, i + 1));
int len = expr.length();
if (pos == 0) ops(num, target, i + 1, cur, cur, expr.append(cur), out);
else {
ops(num, target, i + 1, value + cur, cur, expr.append('+').append(cur), out); expr.setLength(len);
ops(num, target, i + 1, value - cur, -cur, expr.append('-').append(cur), out); expr.setLength(len);
ops(num, target, i + 1, value - last + last * cur, last * cur, expr.append('*').append(cur), out);
}
expr.setLength(len);
}
}
Short answer: Choose 4 segments of length 1–3, each 0–255, with no leading zeros (except "0" itself). Prune when the remaining length can't fit the remaining segments (rem > 3*parts or rem < parts). The search space is constant-bounded (at most 3⁴ = 81 combinations).
void ip(String s, int pos, int part, List<String> parts, List<String> out) {
int rem = s.length() - pos;
if (part == 4) { if (rem == 0) out.add(String.join(".", parts)); return; }
if (rem < 4 - part || rem > 3 * (4 - part)) return;
for (int len = 1; len <= 3 && pos + len <= s.length(); len++) {
String seg = s.substring(pos, pos + len);
if ((seg.length() > 1 && seg.charAt(0) == '0') || Integer.parseInt(seg) > 255) break;
parts.add(seg); ip(s, pos + len, part + 1, parts, out); parts.remove(parts.size() - 1);
}
}
Short answer: Don't generate all the permutations. Use the factorial number system: with k-1 (zero-based), the index of the first digit is k / (n-1)!. Pick and remove that digit, set k %= (n-1)!, and repeat. O(n²) with a list (O(n log n) with a Fenwick tree).
String getPermutation(int n, int k) {
List<Integer> digits = new ArrayList<>(); int[] fact = new int[n + 1]; fact[0] = 1;
for (int i = 1; i <= n; i++) { digits.add(i); fact[i] = fact[i - 1] * i; }
k--; StringBuilder sb = new StringBuilder();
for (int i = n; i >= 1; i--) {
int idx = k / fact[i - 1]; k %= fact[i - 1];
sb.append(digits.remove(idx));
}
return sb.toString();
}
Short answer: In a Gray code, consecutive numbers differ in exactly one bit. The direct formula is g(i) = i ^ (i >> 1) for i in 0..2ⁿ−1: O(2ⁿ). (The recursive reflect-and-prefix construction also works: take the (n−1)-bit list, then append its reverse with the top bit set.)
List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) res.add(i ^ (i >> 1));
return res;
}
Short answer: DFS from node 0, appending to the path; record it at the target, then backtrack. There's no visited set needed, because a DAG has no cycles. The output can be exponential: O(2ⁿ·n) in the worst case.
void paths(int[][] g, int u, List<Integer> path, List<List<Integer>> out) {
path.add(u);
if (u == g.length - 1) out.add(new ArrayList<>(path));
else for (int v : g[u]) paths(g, v, path, out);
path.remove(path.size() - 1);
}
Short answer: Choose each next number's length; reject leading zeros and values over Integer.MAX_VALUE. Once there are two numbers, the next must equal the sum of the previous two: break when the candidate exceeds it (numbers only get bigger as the length increases). Succeed when the whole string is used with at least 3 numbers.
boolean split(String s, int pos, List<Integer> seq) {
if (pos == s.length()) return seq.size() >= 3;
long num = 0;
for (int i = pos; i < s.length(); i++) {
if (i > pos && s.charAt(pos) == '0') break;
num = num * 10 + (s.charAt(i) - '0');
if (num > Integer.MAX_VALUE) break;
int n = seq.size();
if (n >= 2 && num > (long) seq.get(n - 1) + seq.get(n - 2)) break;
if (n < 2 || num == (long) seq.get(n - 1) + seq.get(n - 2)) {
seq.add((int) num);
if (split(s, i + 1, seq)) return true;
seq.remove(seq.size() - 1);
}
}
return false;
}
Short answer: Use a stack (ArrayDeque): push the expected closing bracket for each opening one; on a closing bracket, pop and compare. The string is valid if the stack is empty at the end. O(n). For only (), a counter is enough. (Valid Parentheses)
boolean isValid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') st.push(')'); else if (c == '[') st.push(']'); else if (c == '{') st.push('}');
else if (st.isEmpty() || st.pop() != c) return false;
}
return st.isEmpty();
}
Short answer:
dp[i] = true if there's a j < i with dp[j] true and s[j..i) in the dictionary. O(n²) checks (bounded by the maximum word length).boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words); boolean[] dp = new boolean[s.length() + 1]; dp[0] = true;
for (int i = 1; i <= s.length(); i++)
for (int j = 0; j < i && !dp[i]; j++) dp[i] = dp[j] && dict.contains(s.substring(j, i));
return dp[s.length()];
}
Short answer: Remove the minimum number of characters so that all the valid results come out. BFS by levels: remove one character at a time from each string in the current level (with a visited set); the first level that contains valid strings is the answer, so stop there. (DFS alternative: count the extra ( and ) to remove first, then backtrack with pruning.)
List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>(); Set<String> seen = new HashSet<>(List.of(s));
Queue<String> q = new ArrayDeque<>(List.of(s)); boolean found = false;
while (!q.isEmpty() && !found) {
for (int size = q.size(); size > 0; size--) {
String cur = q.poll();
if (valid(cur)) { res.add(cur); found = true; }
if (found) continue;
for (int i = 0; i < cur.length(); i++) {
char c = cur.charAt(i);
if (c != '(' && c != ')') continue;
String next = cur.substring(0, i) + cur.substring(i + 1);
if (seen.add(next)) q.add(next);
}
}
}
return res;
}
boolean valid(String s) {
int bal = 0;
for (char c : s.toCharArray()) { if (c == '(') bal++; else if (c == ')' && --bal < 0) return false; }
return bal == 0;
}
Q: Why copy the path (new ArrayList<>(path)) when recording a result?
A: The path object is mutated as the search backtracks. Adding it directly would leave every result pointing to the same, eventually empty, list.
Q: How do you avoid duplicate results when the input has repeated values?
A: Sort the input, then skip an element equal to the previous one at the same recursion level (the same start), or, for permutations, when the previous equal element isn't in use.
Q: When does backtracking become dynamic programming? A: When the same sub-problems repeat (overlapping sub-problems), as in word break or partitioning counts. Memoising the result by state turns exponential search into polynomial time.
Q: Why is ArrayDeque preferred over Stack in Java?
A: Stack extends Vector (synchronised, legacy). ArrayDeque is faster, unsynchronised, and is the recommended stack and queue implementation.