Recursion & Backtracking – DSA Notes
9/3/2025
Subsets, combinations, permutations, partitions; classic search problems.
📌 Summary Table
| Problem | Core Idea | Time | Space |
|---|---|---|---|
| Subset Sums | DFS include/exclude, collect sums | O(2ⁿ) | O(n) + output |
| Subset II (Unique Subsets) | Sort + backtrack, skip dupes | O(2ⁿ) | O(n) + output |
| Combinations (n choose k) | Backtrack increasing numbers | ~O(C(n,k)·k) | O(k) + output |
| Combination Sum | Backtrack with reuse of elements | Exponential | O(target depth) |
| Combination Sum II | Sort + skip dupes, single-use | Exponential | O(n) |
| Permutations | Backtrack with used[] | O(n·n!) | O(n) |
| Permutations II | Sort + skip dupes via used[] rule | O(n·n!) | O(n) |
| Letter Case Permutation | Toggle case per letter | O(2^L · n) | O(n) |
| Palindrome Partitioning | Backtrack on cuts + isPal check | ~O(n·2ⁿ) | O(n) |
| K-th Permutation | Factorial number system | O(n²) | O(n) |
| N-Queens | Place by columns, check rows/diagonals | O(n!) | O(n²) board |
| Sudoku Solver | Backtracking with validity checks | Exponential | O(1) board |
| M-Coloring | Try colors 1..m per vertex | O(m^V) | O(V) |
| Rat in a Maze | DFS with visited + path string | Exponential | O(n²) |
| Word Break (DP) | DP over prefixes with set lookup | O(n²) | O(n) |
Notes: “Time/Space” are worst-case asymptotics ignoring output size unless stated.
Subset Sums (All subset totals)
Problem. Return the sum of every subset of the array (in sorted order).
Idea. DFS with two choices at index i: take arr[i] or skip; accumulate sum.
Complexity. O(2ⁿ) sums; recursion depth O(n).
class Solution {
// DFS over index i, accumulating current sum
void dfs(int i, int sum, ArrayList<Integer> arr, ArrayList<Integer> out) {
if (i == arr.size()) { // reached a leaf subset
out.add(sum); // record the sum
return;
}
dfs(i + 1, sum + arr.get(i), arr, out); // include arr[i]
dfs(i + 1, sum, arr, out); // exclude arr[i]
}
ArrayList<Integer> subsetSums(ArrayList<Integer> arr, int N){
ArrayList<Integer> ans = new ArrayList<>();
dfs(0, 0, arr, ans);
Collections.sort(ans); // as required by many judges
return ans;
}
}
Key Takeaway. Classic include/exclude recursion.
Subset II (Unique Subsets)
Problem. Generate all unique subsets when nums may have duplicates.
Idea. Sort, backtrack; at each depth, skip same value when it’s the first pick at that depth.
Complexity. O(2ⁿ) subsets; recursion depth O(n).
class Solution {
void backtrack(int idx, int[] nums, LinkedList<Integer> cur, List<List<Integer>> out) {
out.add(new LinkedList<>(cur)); // record current subset
for (int i = idx; i < nums.length; i++) {
// skip duplicates at the same tree level
if (i > idx && nums[i] == nums[i - 1]) continue;
cur.add(nums[i]);
backtrack(i + 1, nums, cur, out);
cur.removeLast(); // undo choice
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new LinkedList<>();
backtrack(0, nums, new LinkedList<>(), ans);
return ans;
}
}
Key Takeaway. Sort + “skip-same-on-level” to avoid duplicates.
Combinations (n choose k)
Problem. Choose k numbers from 1..n.
Idea. Backtrack from start, pick next strictly larger number.
Complexity. ~O(C(n,k)·k); depth O(k).
class Solution {
void go(int start, int n, int k, List<Integer> cur, List<List<Integer>> out) {
if (cur.size() == k) { out.add(new ArrayList<>(cur)); return; }
// Optional pruning: for (int x = start; x <= n - (k - cur.size()) + 1; x++)
for (int x = start; x <= n; x++) {
cur.add(x);
go(x + 1, n, k, cur, out);
cur.remove(cur.size() - 1);
}
}
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> out = new ArrayList<>();
go(1, n, k, new ArrayList<>(), out);
return out;
}
}
Key Takeaway. Increasing sequence → no duplicates by construction.
Combination Sum (Repetition Allowed)
Problem. Sum to target; use each candidate unbounded times.
Idea. For index idx, either pick (stay at idx) or skip (idx+1).
Complexity. Exponential; depth bounded by target / min(c).
class Solution {
void go(int idx, int[] c, int target, List<Integer> cur, List<List<Integer>> out) {
if (target == 0) { out.add(new ArrayList<>(cur)); return; }
if (idx == c.length || target < 0) return;
// pick c[idx] (reuse allowed)
cur.add(c[idx]);
go(idx, c, target - c[idx], cur, out);
cur.remove(cur.size() - 1);
// skip c[idx]
go(idx + 1, c, target, cur, out);
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> out = new ArrayList<>();
go(0, candidates, target, new ArrayList<>(), out);
return out;
}
}
Key Takeaway. Pick/skip with reuse by not advancing index on pick.
Combination Sum II (Unique)
Problem. Sum to target; each number may be used once; avoid duplicate combinations.
Idea. Sort; iterate from idx; skip duplicates at same depth; no reuse → recurse with i+1.
Complexity. Exponential; pruning with if (c[i] > target) break;.
class Solution {
void go(int idx, int[] c, int target, List<Integer> cur, List<List<Integer>> out) {
if (target == 0) { out.add(new ArrayList<>(cur)); return; }
for (int i = idx; i < c.length; i++) {
if (i > idx && c[i] == c[i - 1]) continue; // skip dupes on level
if (c[i] > target) break; // prune
cur.add(c[i]);
go(i + 1, c, target - c[i], cur, out);
cur.remove(cur.size() - 1);
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> out = new ArrayList<>();
go(0, candidates, target, new ArrayList<>(), out);
return out;
}
}
Key Takeaway. Sort + level-skip and no reuse (i+1).
Permutations (Unique elements)
Problem. All permutations of distinct numbers.
Idea. Backtrack with used[]; choose any unused number.
Complexity. O(n·n!) time, O(n) space.
class Solution {
void go(int[] nums, boolean[] used, List<Integer> cur, List<List<Integer>> out) {
if (cur.size() == nums.length) { out.add(new ArrayList<>(cur)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
cur.add(nums[i]);
go(nums, used, cur, out);
cur.remove(cur.size() - 1);
used[i] = false;
}
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
go(nums, new boolean[nums.length], new ArrayList<>(), out);
return out;
}
}
Key Takeaway. Pick any unused → depth n.
Permutations II (With Duplicates)
Problem. All unique permutations when numbers can repeat.
Idea. Sort; when nums[i]==nums[i-1], only use i if i-1 is used (tree-level skip).
Complexity. O(n·n!) time, O(n) space.
class Solution {
void go(int[] nums, boolean[] used, List<Integer> cur, List<List<Integer>> out) {
if (cur.size() == nums.length) { out.add(new ArrayList<>(cur)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// skip duplicates: don't start a new branch with same value if previous identical not used
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
used[i] = true;
cur.add(nums[i]);
go(nums, used, cur, out);
cur.remove(cur.size() - 1);
used[i] = false;
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> out = new ArrayList<>();
go(nums, new boolean[nums.length], new ArrayList<>(), out);
return out;
}
}
Key Takeaway. Sort + “prev must be used” rule to dedupe.
Letter Case Permutation
Problem. Return all strings by toggling case of alphabetic characters.
Idea. DFS index i: if letter → branch lower/upper; else continue.
Complexity. O(2^L · n) where L letters; depth O(n).
class Solution {
void go(char[] s, int i, List<String> out) {
if (i == s.length) { out.add(new String(s)); return; }
if (Character.isLetter(s[i])) {
s[i] = Character.toLowerCase(s[i]); go(s, i + 1, out);
s[i] = Character.toUpperCase(s[i]); go(s, i + 1, out);
} else {
go(s, i + 1, out);
}
}
public List<String> letterCasePermutation(String s) {
List<String> out = new ArrayList<>();
go(s.toCharArray(), 0, out);
return out;
}
}
Key Takeaway. Branch per letter; digits pass through.
Palindrome Partitioning
Problem. Partition s into all lists of substrings where each part is a palindrome.
Idea. Backtrack over cut positions; check palindrome on the fly.
Complexity. ~O(n·2ⁿ); depth O(n).
class Solution {
boolean isPal(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
void go(int idx, String s, List<String> cur, List<List<String>> out) {
if (idx == s.length()) { out.add(new ArrayList<>(cur)); return; }
for (int i = idx; i < s.length(); i++) {
if (isPal(s, idx, i)) {
cur.add(s.substring(idx, i + 1)); // choose
go(i + 1, s, cur, out); // explore
cur.remove(cur.size() - 1); // un-choose
}
}
}
public List<List<String>> partition(String s) {
List<List<String>> out = new ArrayList<>();
go(0, s, new ArrayList<>(), out);
return out;
}
}
Key Takeaway. Cut only at palindromes to prune.
K-th Permutation of [1..n] (1-indexed)
Problem. Return the k-th permutation in lexicographic order.
Idea. Factorial number system: choose index k / (n-1)!, remove from list, reduce k.
Complexity. O(n²) due to list removals; space O(n).
class Solution {
public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<>();
int fact = 1;
for (int i = 1; i <= n; i++) {
nums.add(i);
if (i < n) fact *= i; // (n-1)!
}
k--; // make k zero-based
StringBuilder sb = new StringBuilder();
while (true) {
int idx = k / fact; // pick block
sb.append(nums.get(idx)); // append chosen digit
nums.remove(idx); // remove from pool
if (nums.isEmpty()) break; // done
k %= fact; // next k inside block
fact /= nums.size(); // next factorial
}
return sb.toString();
}
}
Key Takeaway. Use factoradic indexing.
N-Queens
Problem. Place n queens on an n×n board so none attack each other. Return all boards.
Idea. Place queens column by column; before placing, check row and both diagonals.
Complexity. O(n!) search; space O(n²) board.
class Solution {
// check if we can place at (r,c)
private boolean can(char[][] b, int r, int c) {
// row left
for (int j = 0; j < c; j++) if (b[r][j] == 'Q') return false;
// upper-left diagonal
for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) if (b[i][j] == 'Q') return false;
// lower-left diagonal
for (int i = r + 1, j = c - 1; i < b.length && j >= 0; i++, j--) if (b[i][j] == 'Q') return false;
return true;
}
private void go(int c, char[][] b, List<List<String>> out) {
int n = b.length;
if (c == n) {
List<String> sol = new ArrayList<>();
for (char[] row : b) sol.add(new String(row));
out.add(sol);
return;
}
for (int r = 0; r < n; r++) {
if (can(b, r, c)) {
b[r][c] = 'Q'; // place
go(c + 1, b, out); // next column
b[r][c] = '.'; // backtrack
}
}
}
public List<List<String>> solveNQueens(int n) {
char[][] b = new char[n][n];
for (int i = 0; i < n; i++) Arrays.fill(b[i], '.');
List<List<String>> out = new ArrayList<>();
go(0, b, out);
return out;
}
}
Key Takeaway. Column-wise placement + row/diag checks.
Sudoku Solver
Problem. Fill a 9×9 Sudoku board in-place.
Idea. Find first empty cell; try digits 1..9 that satisfy row/col/box; backtrack.
Complexity. Exponential; practical with pruning.
class Solution {
public void solveSudoku(char[][] board) { solve(board); }
private boolean solve(char[][] b) {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (b[i][j] == '.') {
for (char c = '1'; c <= '9'; c++)
if (valid(b, i, j, c)) {
b[i][j] = c; // place
if (solve(b)) return true; // solve rest
b[i][j] = '.'; // undo
}
return false; // no digit fits here
}
return true; // all filled
}
private boolean valid(char[][] b, int r, int c, char ch) {
for (int k = 0; k < 9; k++)
if (b[r][k] == ch || b[k][c] == ch) return false; // row/col conflict
int br = 3 * (r / 3), bc = 3 * (c / 3);
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (b[br + i][bc + j] == ch) return false; // box conflict
return true;
}
}
Key Takeaway. Choose empty → try valid digit → recurse → undo.
M-Coloring (Graph Coloring)
Problem. Can we color graph vertices with ≤ m colors so adjacent vertices differ?
Idea. DFS assign color 1..m; check adjacency before setting.
Complexity. O(m^V) worst-case; space O(V).
class Solve {
private boolean safe(int node, List<Integer>[] G, int[] color, int c) {
for (int v : G[node]) if (color[v] == c) return false;
return true;
}
private boolean dfs(int idx, List<Integer>[] G, int[] color, int m) {
if (idx == G.length) return true; // all colored
for (int c = 1; c <= m; c++) {
if (safe(idx, G, color, c)) {
color[idx] = c; // choose color
if (dfs(idx + 1, G, color, m)) return true;
color[idx] = 0; // backtrack
}
}
return false;
}
public boolean graphColoring(List<Integer>[] G, int[] color, int m) {
return dfs(0, G, color, m);
}
}
Key Takeaway. Try colors with feasibility check before recursing.
Rat in a Maze
Problem. From (0,0) to (n-1,n-1) in an n×n grid of 0/1, list all paths using moves D/L/R/U, visiting only 1s.
Idea. DFS with visited matrix; append direction on move; backtrack.
Complexity. Exponential; visited uses O(n²).
class Solution {
static void go(int i, int j, int[][] m, int n, String path,
int[][] vis, ArrayList<String> out) {
if (i == n - 1 && j == n - 1) { out.add(path); return; }
int[] di = { +1, 0, 0, -1 }; // D, L, R, U
int[] dj = { 0, -1, +1, 0 };
String dir = "DLRU";
for (int k = 0; k < 4; k++) {
int ni = i + di[k], nj = j + dj[k];
if (ni >= 0 && nj >= 0 && ni < n && nj < n && vis[ni][nj] == 0 && m[ni][nj] == 1) {
vis[i][j] = 1; // mark
go(ni, nj, m, n, path + dir.charAt(k), vis, out); // move
vis[i][j] = 0; // unmark
}
}
}
public static ArrayList<String> findPath(int[][] m, int n) {
ArrayList<String> out = new ArrayList<>();
if (m[0][0] == 1) go(0, 0, m, n, "", new int[n][n], out);
return out;
}
}
Key Takeaway. DFS + visited to avoid cycles; record path as string.
Word Break (DP)
Problem. Can s be segmented into words from dict?
Idea. DP: dp[i] = true if some j < i has dp[j] and s[j..i) is a word.
Complexity. O(n²) time with set lookups, O(n) space.
class Solution {
public boolean wordBreak(String s, List<String> dict) {
HashSet<String> set = new HashSet<>(dict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true; // empty string segmentable
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && set.contains(s.substring(j, i))) {
dp[i] = true;
break; // earliest cut works
}
}
}
return dp[s.length()];
}
}
Key Takeaway. Prefix DP with a dictionary set.