Chapter 10

Backtracking in Java
Java Data Structures & Algorithms Series

Backtracking is recursion with an undo step — you explore a choice, recurse deeper, then undo that
choice and try the next option. It systematically explores all possibilities while pruning invalid
paths early.

1 Backtracking vs Recursion vs DP

Recursion: Solve by breaking into subproblems (no undo needed)

Backtracking: Explore ALL paths, UNDO bad choices ← this chapter
DP: Overlapping subproblems, store results (no undo)

Backtracking = Recursion + Pruning + Undo

The Universal Backtracking Template

void backtrack(state, choices) {

if (goalReached(state)) {
[Link](copy of state); // ← snapshot, NOT reference!
return;
}

for (choice : availableChoices) {

if (isValid(choice)) {
makeChoice(choice); // 1. Choose
backtrack(state, next); // 2. Explore
undoChoice(choice); // 3. Un-choose ← KEY STEP
}
}
}

⭐ The Three-Step Loop:

1. makeChoice() — add to current state
2. backtrack() — go deeper
3. undoChoice() — restore state exactly as it was before step 1

If step 3 is missing or wrong, you get incorrect or duplicate results.

2 Pattern 1 — Subsets (No Duplicates)

Problem: Return all possible subsets of a set with unique integers.

nums = [1,2,3]
Answer: [ [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] ]

public static List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
backtrackSubsets(nums, 0, new ArrayList<>(), result);
return result;
}

private static void backtrackSubsets(int[] nums, int start,

List<Integer> current,
List<List<Integer>> result) {
[Link](new ArrayList<>(current)); // snapshot at EVERY node = valid
subset

for (int i = start; i < [Link]; i++) {

[Link](nums[i]); // choose
backtrackSubsets(nums, i + 1, current, result); // explore
[Link]([Link]() - 1); // un-choose
}
}

// Time: O(2^n × n) | Space: O(n)

3 Pattern 2 — Subsets II (With Duplicates)

Problem: Array may contain duplicates. Return only unique subsets.

nums = [1,2,2]
Answer: [ [], [1], [2], [1,2], [2,2], [1,2,2] ] ← no duplicate [2]

public static List<List<Integer>> subsetsWithDup(int[] nums) {

[Link](nums); // sort first to group duplicates adjacent
List<List<Integer>> result = new ArrayList<>();
backtrackSubsDup(nums, 0, new ArrayList<>(), result);
return result;
}

private static void backtrackSubsDup(int[] nums, int start,

List<Integer> current,
List<List<Integer>> result) {
[Link](new ArrayList<>(current));

for (int i = start; i < [Link]; i++) {

if (i > start && nums[i] == nums[i-1]) continue; // skip duplicate branch

[Link](nums[i]);
backtrackSubsDup(nums, i + 1, current, result);
[Link]([Link]() - 1);
}
}

// Time: O(2^n × n) | Space: O(n)

⭐ Duplicate-Skip Rule: if (i > start && nums[i] == nums[i-1]) continue
This skips making the same choice again at the SAME recursion level.
It does NOT skip the element across different levels — that is intentional.

4 Pattern 3 — Combination Sum I (Reuse Allowed)

Problem: Find all combinations summing to target. Each number can be used unlimited times.

candidates=[2,3,6,7], target=7
Answer: [ [2,2,3], [7] ]

public static List<List<Integer>> combinationSum(int[] candidates, int target) {

[Link](candidates);
List<List<Integer>> result = new ArrayList<>();
backtrackComb(candidates, 0, target, new ArrayList<>(), result);
return result;
}

private static void backtrackComb(int[] candidates, int start, int remaining,

List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
[Link](new ArrayList<>(current));
return;
}

for (int i = start; i < [Link]; i++) {

if (candidates[i] > remaining) break; // sorted → prune rest

[Link](candidates[i]);
backtrackComb(candidates, i, remaining - candidates[i], current, result);
// ↑ pass i (not i+1) to allow reusing the same element
[Link]([Link]() - 1);
}
}

// Time: O(2^target) | Space: O(target / min_candidate)

5 Pattern 4 — Combination Sum II (No Reuse, With Duplicates)

Problem: Each number used at most once. Array may have duplicates. Return unique combinations.

candidates=[10,1,2,7,6,1,5], target=8
Answer: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

public static List<List<Integer>> combinationSum2(int[] candidates, int target) {

[Link](candidates);
List<List<Integer>> result = new ArrayList<>();
 backtrackComb2(candidates, 0, target, new ArrayList<>(), result);
return result;
}

private static void backtrackComb2(int[] candidates, int start, int remaining,

List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
[Link](new ArrayList<>(current));
return;
}

for (int i = start; i < [Link]; i++) {

if (candidates[i] > remaining) break; // pruning
if (i > start && candidates[i] == candidates[i-1]) continue; // skip dup

[Link](candidates[i]);
backtrackComb2(candidates, i + 1, remaining - candidates[i], current,
result);
// ↑ pass i+1 (not i) because each element used at most once
[Link]([Link]() - 1);
}
}

// Time: O(2^n × n) | Space: O(n)

6 Pattern 5 — Permutations I (No Duplicates)

public static List<List<Integer>> permute(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
backtrackPerm(nums, new ArrayList<>(), new boolean[[Link]], result);
return result;
}

private static void backtrackPerm(int[] nums, List<Integer> current,

boolean[] used, List<List<Integer>> result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current));
return;
}

for (int i = 0; i < [Link]; i++) {

if (used[i]) continue;

used[i] = true;
[Link](nums[i]);
backtrackPerm(nums, current, used, result);
[Link]([Link]() - 1); // un-choose
used[i] = false; // un-mark
}
}

// Time: O(n! × n) | Space: O(n)

 7 Pattern 6 — Permutations II (With Duplicates)

Problem: Array may have duplicates. Return only unique permutations.

nums = [1,1,2]
Answer: [ [1,1,2], [1,2,1], [2,1,1] ]

public static List<List<Integer>> permuteUnique(int[] nums) {

[Link](nums); // sort to group duplicates
List<List<Integer>> result = new ArrayList<>();
backtrackPermUniq(nums, new ArrayList<>(), new boolean[[Link]], result);
return result;
}

private static void backtrackPermUniq(int[] nums, List<Integer> current,

boolean[] used, List<List<Integer>> result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current));
return;
}

for (int i = 0; i < [Link]; i++) {

if (used[i]) continue;
// Allow nums[i] only if nums[i-1] (same value) was used in this branch
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

used[i] = true;
[Link](nums[i]);
backtrackPermUniq(nums, current, used, result);
[Link]([Link]() - 1);
used[i] = false;
}
}

// Time: O(n! × n) | Space: O(n)

8 Pattern 7 — N-Queens

Problem: Place N queens on an N×N board so no two queens share a row, column, or diagonal.

N=4 has 2 solutions:

. Q . . . . Q .
. . . Q or Q . . .
Q . . . . . . Q
. . Q . . Q . .

public static List<List<String>> solveNQueens(int n) {

List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) [Link](row, '.');
backtrackQueens(board, 0, result);
return result;
}
private static void backtrackQueens(char[][] board, int row,
List<List<String>> result) {
if (row == [Link]) {
List<String> sol = new ArrayList<>();
for (char[] r : board) [Link](new String(r));
[Link](sol);
return;
}

for (int col = 0; col < [Link]; col++) {

if (isSafe(board, row, col)) {
board[row][col] = 'Q'; // place
backtrackQueens(board, row + 1, result);
board[row][col] = '.'; // remove (backtrack)
}
}
}

private static boolean isSafe(char[][] board, int row, int col) {

int n = [Link];
for (int i = 0; i < row; i++)
if (board[i][col] == 'Q') return false; // column check
for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)
if (board[i][j] == 'Q') return false; // upper-left diagonal
for (int i=row-1, j=col+1; i>=0 && j<n; i--, j++)
if (board[i][j] == 'Q') return false; // upper-right diagonal
return true;
}

// Time: O(n!) | Space: O(n²)

9 Pattern 8 — Sudoku Solver

Problem: Fill a 9×9 Sudoku grid so every row, column, and 3×3 box contains digits 1–9 exactly once.

public static void solveSudoku(char[][] board) {

solve(board);
}

private static boolean solve(char[][] board) {

for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] != '.') continue; // cell already filled

for (char num = '1'; num <= '9'; num++) {

if (isValid(board, row, col, num)) {
board[row][col] = num; // place digit
if (solve(board)) return true; // recurse — found solution
board[row][col] = '.'; // backtrack
}
}
return false; // no digit works → signal caller to backtrack
}
}
return true; // all cells filled → solution found
}
private static boolean isValid(char[][] board, int row, int col, char num) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == num) return false; // row conflict
if (board[i][col] == num) return false; // column conflict
int boxRow = 3 * (row / 3) + i / 3;
int boxCol = 3 * (col / 3) + i % 3;
if (board[boxRow][boxCol] == num) return false; // 3×3 box conflict
}
return true;
}

// Time: O(9^empty_cells) | Space: O(81) = O(1)

10 Pattern 9 — Word Search

Problem: Find if a word exists in a 2D board using adjacent (up/down/left/right) cells. Each cell
used once.

board=[["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
word="ABCCED" → true

public static boolean exist(char[][] board, String word) {

int m = [Link], n = board[0].length;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (dfsWord(board, word, i, j, 0)) return true;
return false;
}

private static boolean dfsWord(char[][] board, String word,

int r, int c, int idx) {
if (idx == [Link]()) return true; // all chars matched

if (r < 0 || r >= [Link] ||

c < 0 || c >= board[0].length) return false; // out of bounds
if (board[r][c] != [Link](idx)) return false; // char mismatch

char temp = board[r][c];

board[r][c] = '#'; // mark visited — prevent reuse in same path

boolean found = dfsWord(board, word, r+1, c, idx+1) ||

dfsWord(board, word, r-1, c, idx+1) ||
dfsWord(board, word, r, c+1, idx+1) ||
dfsWord(board, word, r, c-1, idx+1);

board[r][c] = temp; // restore cell (backtrack)

return found;
}

// Time: O(m × n × 4^L) L = word length | Space: O(L)

 11 Pattern 10 — Palindrome Partitioning

Problem: Partition a string so every substring in the partition is a palindrome.

s = "aab"
Answer: [ ["a","a","b"], ["aa","b"] ]

public static List<List<String>> partition(String s) {

List<List<String>> result = new ArrayList<>();
backtrackPalin(s, 0, new ArrayList<>(), result);
return result;
}

private static void backtrackPalin(String s, int start,

List<String> current,
List<List<String>> result) {
if (start == [Link]()) {
[Link](new ArrayList<>(current));
return;
}

for (int end = start + 1; end <= [Link](); end++) {

String sub = [Link](start, end);
if (isPalin(sub)) {
[Link](sub); // choose
backtrackPalin(s, end, current, result); // explore
[Link]([Link]() - 1); // un-choose
}
}
}

private static boolean isPalin(String s) {

int l = 0, r = [Link]() - 1;
while (l < r) if ([Link](l++) != [Link](r--)) return false;
return true;
}

// Time: O(n × 2^n) | Space: O(n)

12 Pattern 11 — Letter Combinations of a Phone Number

digits = "23"
Answer: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

public static List<String> letterCombinations(String digits) {

if ([Link]()) return new ArrayList<>();

String[] phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

List<String> result = new ArrayList<>();
backtrackPhone(digits, 0, new StringBuilder(), phone, result);
return result;
}

private static void backtrackPhone(String digits, int idx,

StringBuilder current,
String[] phone, List<String> result) {
if (idx == [Link]()) {
[Link]([Link]());
return;
}

String letters = phone[[Link](idx) - '0'];

for (char c : [Link]()) {
[Link](c); // choose
backtrackPhone(digits, idx + 1, current, phone, result); // explore
[Link]([Link]() - 1); // un-choose
}
}

// Time: O(4^n × n) | Space: O(n)

13 Backtracking Pruning Strategies

The key to efficient backtracking is aggressive pruning — cutting branches early rather than
exploring them to the end.

Strategy How to Apply Example

Sort first [Link]() before backtracking Break when candidates[i] >
remaining
Skip duplicates if (i > start && nums[i] == nums[i- Subsets II, Combination Sum II
1])
Early termination if (candidates[i] > remaining) Combination Sum I / II
break
Visited array boolean[] used or mark cell with Permutations, Word Search
#
Bounds check if (r < 0 || c < 0 || ...) return Flood Fill, Word Search, N-
Queens

14 Full Runnable Java Program

import [Link].*;

public class Chapter10Backtracking {

public static void main(String[] args) {

[Link]("Subsets [1,2,3]: " + subsets(new int[]
{1,2,3}));
[Link]("Subsets w/dup [1,2,2]: " + subsetsWithDup(new int[]
{1,2,2}));
[Link]("CombSum [2,3,6,7] t=7: " + combinationSum(new int[]
{2,3,6,7}, 7));
[Link]("CombSum2 [10,1,2,7,6,1,5] t=8: " + combinationSum2(new
int[]{10,1,2,7,6,1,5}, 8));
[Link]("Permutations [1,2,3]: " + permute(new int[]
{1,2,3}));
[Link]("PermuteUnique [1,1,2]: " + permuteUnique(new int[]
{1,1,2}));
[Link]("N-Queens N=4: " + solveNQueens(4));

char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};

[Link]("Word ABCCED: " + exist(board, "ABCCED"));
// true

[Link]("Palindrome partition 'aab': " + partition("aab"));

[Link]("Phone '23': " +
letterCombinations("23"));
}

static List<List<Integer>> subsets(int[] n){List<List<Integer>> r=new

ArrayList<>();btS(n,0,new ArrayList<>(),r);return r;}
static void btS(int[] n,int s,List<Integer> c,List<List<Integer>> r){[Link](new
ArrayList<>(c));for(int i=s;i<[Link];i++)
{[Link](n[i]);btS(n,i+1,c,r);[Link]([Link]()-1);}}

static List<List<Integer>> subsetsWithDup(int[] n)

{[Link](n);List<List<Integer>> r=new ArrayList<>();btSD(n,0,new
ArrayList<>(),r);return r;}
static void btSD(int[] n,int s,List<Integer> c,List<List<Integer>> r){[Link](new
ArrayList<>(c));for(int i=s;i<[Link];i++){if(i>s&&n[i]==n[i-
1])continue;[Link](n[i]);btSD(n,i+1,c,r);[Link]([Link]()-1);}}

static List<List<Integer>> combinationSum(int[] c,int t)

{[Link](c);List<List<Integer>> r=new ArrayList<>();btC(c,0,t,new
ArrayList<>(),r);return r;}
static void btC(int[] c,int s,int rem,List<Integer> cur,List<List<Integer>> r)
{if(rem==0){[Link](new ArrayList<>(cur));return;}for(int i=s;i<[Link];i++)
{if(c[i]>rem)break;[Link](c[i]);btC(c,i,rem-c[i],cur,r);[Link]([Link]()-1);}}

static List<List<Integer>> combinationSum2(int[] c,int t)

{[Link](c);List<List<Integer>> r=new ArrayList<>();btC2(c,0,t,new
ArrayList<>(),r);return r;}
static void btC2(int[] c,int s,int rem,List<Integer> cur,List<List<Integer>> r)
{if(rem==0){[Link](new ArrayList<>(cur));return;}for(int i=s;i<[Link];i++)
{if(c[i]>rem)break;if(i>s&&c[i]==c[i-1])continue;[Link](c[i]);btC2(c,i+1,rem-
c[i],cur,r);[Link]([Link]()-1);}}

static List<List<Integer>> permute(int[] nums){List<List<Integer>> r=new

ArrayList<>();btP(nums,new ArrayList<>(),new boolean[[Link]],r);return r;}
static void btP(int[] n,List<Integer> c,boolean[] u,List<List<Integer>> r)
{if([Link]()==[Link]){[Link](new ArrayList<>(c));return;}for(int i=0;i<[Link];i+
+){if(u[i])continue;u[i]=true;[Link](n[i]);btP(n,c,u,r);[Link]([Link]()-
1);u[i]=false;}}

static List<List<Integer>> permuteUnique(int[] nums)

{[Link](nums);List<List<Integer>> r=new ArrayList<>();btPU(nums,new
ArrayList<>(),new boolean[[Link]],r);return r;}
static void btPU(int[] n,List<Integer> c,boolean[] u,List<List<Integer>> r)
{if([Link]()==[Link]){[Link](new ArrayList<>(c));return;}for(int i=0;i<[Link];i+
+){if(u[i])continue;if(i>0&&n[i]==n[i-1]&&!u[i-
1])continue;u[i]=true;[Link](n[i]);btPU(n,c,u,r);[Link]([Link]()-1);u[i]=false;}}

static List<List<String>> solveNQueens(int n){List<List<String>> r=new

ArrayList<>();char[][] b=new char[n][n];for(char[]
row:b)[Link](row,'.');btQ(b,0,r);return r;}
static void btQ(char[][] b,int row,List<List<String>> r){if(row==[Link])
{List<String> s=new ArrayList<>();for(char[] c:b)[Link](new
String(c));[Link](s);return;}for(int c=0;c<[Link];c++){if(safe(b,row,c)){b[row]
[c]='Q';btQ(b,row+1,r);b[row][c]='.';}}}
static boolean safe(char[][] b,int r,int c){int n=[Link];for(int i=0;i<r;i+
+)if(b[i][c]=='Q')return false;for(int i=r-1,j=c-1;i>=0&&j>=0;i--,j--)if(b[i]
[j]=='Q')return false;for(int i=r-1,j=c+1;i>=0&&j<n;i--,j++)if(b[i][j]=='Q')return
false;return true;}

static boolean exist(char[][] b,String w){for(int i=0;i<[Link];i++)for(int

j=0;j<b[0].length;j++)if(dfs(b,w,i,j,0))return true;return false;}
static boolean dfs(char[][] b,String w,int r,int c,int idx)
{if(idx==[Link]())return true;if(r<0||r>=[Link]||c<0||c>=b[0].length||b[r][c]!
=[Link](idx))return false;char t=b[r][c];b[r][c]='#';boolean
f=dfs(b,w,r+1,c,idx+1)||dfs(b,w,r-1,c,idx+1)||dfs(b,w,r,c+1,idx+1)||dfs(b,w,r,c-
1,idx+1);b[r][c]=t;return f;}

static List<List<String>> partition(String s){List<List<String>> r=new

ArrayList<>();btPalin(s,0,new ArrayList<>(),r);return r;}
static void btPalin(String s,int st,List<String> c,List<List<String>> r)
{if(st==[Link]()){[Link](new ArrayList<>(c));return;}for(int
e=st+1;e<=[Link]();e++){String sub=[Link](st,e);if(isPalin(sub))
{[Link](sub);btPalin(s,e,c,r);[Link]([Link]()-1);}}}
static boolean isPalin(String s){int l=0,r=[Link]()-1;while(l<r)if([Link](l+
+)!=[Link](r--))return false;return true;}

static List<String> letterCombinations(String d){if([Link]())return new

ArrayList<>();String[]
ph={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> r=new
ArrayList<>();btPh(d,0,new StringBuilder(),ph,r);return r;}
static void btPh(String d,int idx,StringBuilder c,String[] ph,List<String> r)
{if(idx==[Link]()){[Link]([Link]());return;}for(char
ch:ph[[Link](idx)-'0'].toCharArray())
{[Link](ch);btPh(d,idx+1,c,ph,r);[Link]([Link]()-1);}}
}

15 Practice Problems for Chapter 10

Solve in this order:

Difficulty Problem
Medium Subsets (LeetCode #78)
Medium Subsets II (LeetCode #90)
Medium Combination Sum I (LeetCode #39)
Medium Combination Sum II (LeetCode #40)
Medium Permutations (LeetCode #46)
Medium Permutations II (LeetCode #47)
Medium Letter Combinations of Phone Number (LeetCode
#17)
Medium Palindrome Partitioning (LeetCode #131)
Medium Word Search (LeetCode #79)
Hard N-Queens (LeetCode #51)
Hard Sudoku Solver (LeetCode #37)

16 Backtracking Problem Classification

Problem Type Trigger Keywords Key Template Point

Subsets All subsets, power set Add snapshot at EVERY node
Combinations Choose K from N, sum to target Add snapshot only at leaves
Permutations All arrangements, all orders Use boolean used[] array
Grid problems 2D board, path, connected region Mark visited (#), restore after
Constraint satisfaction N-Queens, Sudoku, valid Check validity BEFORE placing
placement
String partition Split into valid Try every split point
palindromes/words end=start+1..n

💡 Key Insight: Two bugs account for 90% of wrong backtracking answers:

Bug 1 — Wrong snapshot: [Link](current) instead of [Link](new ArrayList<>(current))

You added a reference. When you backtrack, current changes, corrupting all saved states.

Bug 2 — Incomplete undo: forgetting to restore state after recursion.

The undo step must mirror the choose step exactly.

If your solution gives wrong or duplicate results, check these two things first.

Next up is Chapter 11 — Strings! 🚀