Home/DSA Complete from Scratch to Expert/dsa-topics

Backtracking

Master this topic with zero to advance depth.

Combination Sum

The Goal: Finding Target Sum

Given an array of distinct integers candidates and a target integer, find all unique combinations where the chosen numbers sum to target. You may return the combinations in any order.

Key Rule: Unlimited Re-use

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Decision Tree Branching

At each step, you can either:

Use the current element: Subtract its value from the target and stay at the same index (because we can re-use it).
Skip the current element: Move to the next index in the array.

Find all unique combinations in candidates that sum to target (reuse allowed). Includes visual decision tree.

Medium

Examples

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Approach 1

Level I: Basic Backtracking (Include/Exclude)

Intuition

At every step, we either include the current candidate or move to the next candidate.

We use recursion to explore the decision tree. If target == 0, we found a valid combination. If target < 0 or we've used all candidates, we backtrack.

⏱ O(2^T) where T is the target sum.💾 O(T/min_val) for the recursion stack.

Detailed Dry Run

Dry Run: target=7, candidates=[2,3]
| Step | idx | target | path    | Action            |
| :--- | :-- | :----- | :------ | :---------------- |
| 1    | 0   | 7      | []      | Start             |
| 2    | 0   | 5      | [2]     | Use 2             |
| 3    | 0   | 3      | [2,2]   | Use 2             |
| 4    | 0   | 1      | [2,2,2] | Use 2             |
| 5    | 0   | -1     | [2,2,2] | FAIL (Backtrack)  |
| 6    | 1   | 1      | [2,2]   | Skip 2, Try 3     |
| 7    | 1   | -2     | [2,2,3] | FAIL (Backtrack)  |
| 8    | 1   | 7      | []      | Skip all for id=0 |

java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, target, new ArrayList<>(), candidates, result);
        return result;
    }
    private void backtrack(int idx, int target, List<Integer> current, int[] candidates, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (idx == candidates.length || target < 0) return;
        
        // Use current candidate
        current.add(candidates[idx]);
        backtrack(idx, target - candidates[idx], current, candidates, result);
        current.remove(current.size() - 1);
        
        // Skip current candidate
        backtrack(idx + 1, target, current, candidates, result);
    }
}

Approach 2

Level II: Optimized Backtracking (Loop-Based + Sorting)

Intuition

Sorting the candidates allows us to break early from the loop once the target is exceeded.

For each call, iterate through candidates from the current index to the end. If target - candidates[i] < 0, stop the loop (pruning).

⏱ O(N^(T/M + 1)) where M is the min value.💾 O(T/M)

Detailed Dry Run

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

Try 2. Recurse 5. Try 2. Recurse 3. Try 2. Recurse 1. Try 2 (FAIL - 3rd 2 is fine, 4th fails). Break.
Backtrack to target 3. Try 3. Recurse 0. SUCCESS [2,2,3].

java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, target, new ArrayList<>(), candidates, result);
        return result;
    }
    private void backtrack(int start, int target, List<Integer> current, int[] candidates, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break; // Pruning
            current.add(candidates[i]);
            backtrack(i, target - candidates[i], current, candidates, result);
            current.remove(current.size() - 1);
        }
    }
}

Approach 3

Level III: Iterative DP (Unbounded Knapsack Style)

Intuition

Since we only care about the values and can reuse items, we can use a DP table where dp[i] stores all unique combinations summing to i.

Initialize dp[0] with an empty combination. For each candidate, iterate from candidate to target, adding the candidate to all combinations in dp[i - candidate] and storing them in dp[i].

⏱ O(N * T * C) where C is the number of combinations.💾 O(T * C)

Detailed Dry Run

target=3, candidates=[1,2]

dp[0] = [[]], dp[1,2,3] = []
Use 1: dp[1]=[[1]], dp[2]=[[1,1]], dp[3]=[[1,1,1]]
Use 2: dp[2]=[[1,1],[2]], dp[3]=[[1,1,1],[1,2]]

java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int i = 0; i <= target; i++) dp.add(new ArrayList<>());
        dp.get(0).add(new ArrayList<>());
        
        for (int c : candidates) {
            for (int i = c; i <= target; i++) {
                for (List<Integer> comb : dp.get(i - c)) {
                    List<Integer> newComb = new ArrayList<>(comb);
                    newComb.add(c);
                    dp.get(i).add(newComb);
                }
            }
        }
        return dp.get(target);
    }
}

Permutations

Exploration vs. Selection

In permutation problems, the goal is to arrange all elements of a set in every possible order. Unlike combinations, the order matters here ([1, 2] is different from [2, 1]).

Key Backtracking Strategies

Visited Array: Maintain a boolean array to track which elements are already included in the current permutation. This is intuitive but uses extra space.
Swap-Based: Swap the current element with every element to its right, recurse, and then swap back. This is highly efficient as it uses the input array for state.

Given an array nums of distinct integers, return all possible permutations. Includes visual state-space tree.

Medium

Examples

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Approach 1

Level I: Backtracking with Visited Array

Intuition

Maintain a list of 'remaining' elements or a boolean array to track usage.

Iterate through all numbers. If a number is not visited, add it to the current permutation, mark it visited, and recurse. Unmark and remove after recursion.

⏱ O(N * N!)💾 O(N) for recursion stack and visited array.

Detailed Dry Run

Dry Run: nums=[1,2]
| Path  | Visited | Action             |
| :---  | :---    | :---               |
| []    | {F, F}  | Start              |
| [1]   | {T, F}  | Choose 1           |
| [1,2] | {T, T}  | Choose 2 (Result!) |
| [1]   | {T, F}  | Backtrack          |
| []    | {F, F}  | Backtrack          |
| [2]   | {F, T}  | Choose 2           |
| [2,1] | {T, T}  | Choose 1 (Result!) |

java

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

Approach 2

Level II: Backtracking with Swapping (In-Place)

Intuition

Instead of a visited array, we can rearrange the input array itself to represent the current state.

At index first, swap nums[first] with every element from first to N-1. Recurse for first + 1. This 'fixes' one element and permutes the rest.

⏱ O(N * N!)💾 O(N) for recursion stack.

Detailed Dry Run

nums=[1,2,3], first=0

Swap(0,0): nums=[1,2,3]. Recurse first=1. 2. Swap(1,1): nums=[1,2,3]. Recurse first=2. SUCCESS [1,2,3]. 3. Swap(1,2): nums=[1,3,2]. Recurse first=2. SUCCESS [1,3,2].
Swap(0,1): nums=[2,1,3]. Recurse first=1...

java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (int n : nums) list.add(n);
        backtrack(0, list, res);
        return res;
    }
    private void backtrack(int first, List<Integer> nums, List<List<Integer>> res) {
        if (first == nums.size()) {
            res.add(new ArrayList<>(nums));
            return;
        }
        for (int i = first; i < nums.size(); i++) {
            Collections.swap(nums, first, i);
            backtrack(first + 1, nums, res);
            Collections.swap(nums, first, i); // Backtrack
        }
    }
}

Approach 3

Level III: Iterative Lexicographical Order

Intuition

Generate permutations in lexicographical order. This is useful when the input is sorted or we need to find the 'next' permutation.

Start with the smallest permutation (sorted). Repeatedly find the next lexicographical permutation until we return to the start.

⏱ O(N * N!)💾 O(1) extra space.

Detailed Dry Run

nums=[1,2,3]

Initial: [1,2,3]
Next: [1,3,2]
Next: [2,1,3]
Next: [2,3,1]
Next: [3,1,2]
Next: [3,2,1]

java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        do {
            List<Integer> list = new ArrayList<>();
            for (int n : nums) list.add(n);
            res.add(list);
        } while (nextPermutation(nums));
        return res;
    }
    private boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) i--;
        if (i < 0) return false;
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
        reverse(nums, i + 1);
        return true;
    }
    private void swap(int[] nums, int i, int j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) swap(nums, i++, j--);
    }
}

Subsets

The Power Set

A power set of $S$ is the set of all subsets of $S$ , including the empty set and $S$ itself. For a set with $n$ elements, there are $2^n$ subsets.

Inclusion-Exclusion Principle

At each step, we have two choices for the current element: either include it in the current subset or exclude it.

Generate all possible subsets (the power set) of a set of unique integers. Includes visual inclusion-exclusion trace.

Medium

Examples

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Approach 1

Level I: Recursive Backtracking (Include/Exclude)

Intuition

At each step, we decide whether to add nums[i] to our subset or not.

Use a recursive function dfs(idx, current). In one branch, add nums[idx] and recurse. In the other, don't add it and recurse.

⏱ O(N * 2^N)💾 O(N) for recursion stack.

Detailed Dry Run

Dry Run: nums=[1,2]
| idx | path  | Decision | Next State |
| :-- | :---: | :---     | :---       |
| 0   | []    | Include 1| DFS(1, [1])|
| 1   | [1]   | Include 2| DFS(2, [1,2]) -> RES: [1,2]|
| 1   | [1]   | Exclude 2| DFS(2, [1]) -> RES: [1]|
| 0   | []    | Exclude 1| DFS(1, []) |
| 1   | []    | Include 2| DFS(2, [2]) -> RES: [2]|
| 1   | []    | Exclude 2| DFS(2, []) -> RES: []|

java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, res);
        return res;
    }
    private void backtrack(int idx, List<Integer> current, int[] nums, List<List<Integer>> res) {
        if (idx == nums.length) {
            res.add(new ArrayList<>(current));
            return;
        }
        current.add(nums[idx]);
        backtrack(idx + 1, current, nums, res);
        current.remove(current.size() - 1);
        backtrack(idx + 1, current, nums, res);
    }
}

Approach 2

Level II: Cascading (Iterative Generation)

Intuition

Start with an empty set and gradually build the power set.

Start with [[]]. For each number in nums, duplicate all existing subsets and add the current number to the duplicates.

⏱ O(N * 2^N)💾 O(N * 2^N) to store subsets.

Detailed Dry Run

nums=[1,2]

res = [[]]
num=1: res = [[], [1]]
num=2: res = [[], [1], [2], [1,2]]

java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int n : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> subset = new ArrayList<>(res.get(i));
                subset.add(n);
                res.add(subset);
            }
        }
        return res;
    }
}

Approach 3

Level III: Bit Manipulation (Bitmask)

Intuition

Each subset of a set with $N$ elements can be uniquely mapped to a binary number from $0$ to $2^N - 1$ .

Loop from i = 0 to 2^N - 1. For each i, if the $j$ -th bit is 1, include nums[j] in the current subset.

⏱ O(N * 2^N)💾 O(N * 2^N)

Detailed Dry Run

nums=[1,2]

i=0 (00): []
i=1 (01): [1]
i=2 (10): [2]
i=3 (11): [1,2]

java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) subset.add(nums[j]);
            }
            res.add(subset);
        }
        return res;
    }
}

Subsets II

Handling Duplicates

When the input array contains duplicates, the standard power set logic generates duplicate subsets. To avoid this, we must sort the array and skip identical elements during the recursion.

The Skip Condition

If nums[i] == nums[i-1] and we are at the same recursive level (not following the inclusion branch), we skip the current element to avoid repeating the same starting subset.

Generate all possible subsets of an integer array that may contain duplicates. Includes visual duplicate-skipping trace.

Medium

Examples

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Approach 1

Level I: Backtracking with Sorting

Intuition

Sort and skip duplicates to ensure uniqueness.

Sort the array first. In the loop-based backtracking, if i > start and nums[i] == nums[i-1], we skip to the next iteration.

⏱ O(N * 2^N)💾 O(N)

Detailed Dry Run

nums=[1,2,2], start=1
1. i=1, pick nums[1]=2 -> subset [1,2]
2. i=2, nums[2]==nums[1], skip!

java

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

Letter Combinations of a Phone Number

Cartesion Product on Strings

This problem asks for the Cartesian product of several sets of characters. Each digit from 2-9 maps to a set of letters (like a telephone keypad).

Key Backtracking Logic

We iterate through the input digits. For the current digit, we try all mapped letters, appending them to our current path, and moving to the next digit.

Decision Tree Width

The width of the tree varies: 3 for most digits (2, 3, 4, 5, 6, 8), and 4 for digits '7' (pqrs) and '9' (wxyz).

Find all letter combinations for a phone number. Includes visual Cartesian product tree.

Medium

Examples

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

Approach 1

Level I: Recursive Backtracking

Intuition

Treat the problem as a tree traversal where each digit is a level and each letter is a branch.

Maintain a mapping of digits to letters. At each call backtrack(idx, path), if idx == digits.length, add path to results. Otherwise, iterate through letters of digits[idx] and recurse.

⏱ O(4^N * N) where N is the length of digits.💾 O(N) for recursion stack.

Detailed Dry Run

Dry Run: digits="2"
| idx | Digit | Letter | Path | Action             |
| :-- | :---- | :----- | :--- | :----------------- |
| 0   | '2'   | 'a'    | "a"  | Choose 'a', DFS(1) |
| 1   | -     | -      | "a"  | Result! (Backtrack)|
| 0   | '2'   | 'b'    | "b"  | Choose 'b', DFS(1) |
| 1   | -     | -      | "b"  | Result! (Backtrack)|
| 0   | '2'   | 'c'    | "c"  | Choose 'c', DFS(1) |

java

class Solution {
    private final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.isEmpty()) return res;
        backtrack(0, new StringBuilder(), digits, res);
        return res;
    }
    private void backtrack(int idx, StringBuilder path, String digits, List<String> res) {
        if (idx == digits.length()) {
            res.add(path.toString());
            return;
        }
        String letters = MAP[digits.charAt(idx) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(idx + 1, path, digits, res);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

Approach 2

Level II: Iterative BFS (Queue-based)

Intuition

Instead of recursion, use a queue to store intermediate combinations.

Initialize queue with an empty string. For each digit, dequeue all strings, append each possible letter for that digit, and enqueue the new strings.

⏱ O(4^N * N)💾 O(4^N)

Detailed Dry Run

digits="23"

Queue: [""]
Digit '2': Dequeue "", Enqueue "a", "b", "c". Queue: ["a", "b", "c"]
Digit '3': Dequeue "a", Enqueue "ad", "ae", "af". Queue: ["b", "c", "ad", "ae", "af"]...

java

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> queue = new LinkedList<>();
        if (digits.isEmpty()) return queue;
        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            int d = digits.charAt(i) - '0';
            while (queue.peek().length() == i) {
                String s = queue.remove();
                for (char c : map[d].toCharArray()) queue.add(s + c);
            }
        }
        return queue;
    }
}

Approach 3

Level III: Optimized Backtracking (String Sharing / Buffer)

Intuition

In some languages, creating many small strings is expensive. Using a shared buffer can improve performance.

Use a StringBuilder (Java) or a fixed-size array and only convert to result strings at the leaves of the tree.

⏱ O(4^N * N)💾 O(N)

Detailed Dry Run

Same as Level I, but focusing on memory alloc efficiency.

java

// Same as Level I Java code, which already uses StringBuilder for efficiency.

Word Search

Backtracking on 2D Grids

This problem is a classic example of DFS on a grid. We need to find a sequence of adjacent cells that match the characters of a given word.

Core Rules

Use each cell at most once per word (requires tracking visited cells).
Move in four directions: Up, Down, Left, Right.

Performance Optimization

To avoid using $O(M \times N)$ extra space for a visited array, we can temporarily modify the board with a special character (like '#') to mark a cell as visited, then restore it after recursion (Backtracking).

Find a word in a 2D grid using DFS. Includes visual traversal trace.

Medium

Examples

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

Approach 1

Level I: DFS Backtracking (Visited Set)

Intuition

Try starting at every cell $(i, j)$ . If it matches word[0], explore its neighbors recursively.

Use a visited set to keep track of used cells in the current path. If we match all characters of the word, return true.

⏱ O(N * M * 3^L) where L is the length of the word.💾 O(L) for recursion stack.

Detailed Dry Run

Dry Run: board=[['A','B'],['C','D']], word="ABD"
| Step | Cell  | Char | Path | Action           |
| :--- | :---: | :--- | :--- | :--------------- |
| 1    | (0,0) | 'A'  | "A"  | Match, try neighbors |
| 2    | (0,1) | 'B'  | "AB" | Match, try neighbors |
| 3    | (1,1) | 'D'  | "ABD"| Match! SUCCESS   |
| 4    | (1,0) | 'C'  | -    | No Match (from A) |

java

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(0, i, j, board, word, visited)) return true;
            }
        }
        return false;
    }
    private boolean dfs(int idx, int r, int c, char[][] board, String word, boolean[][] visited) {
        if (idx == word.length()) return true;
        if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || visited[r][c] || board[r][c] != word.charAt(idx)) return false;
        
        visited[r][c] = true;
        boolean found = dfs(idx + 1, r + 1, c, board, word, visited) ||
                        dfs(idx + 1, r - 1, c, board, word, visited) ||
                        dfs(idx + 1, r, c + 1, board, word, visited) ||
                        dfs(idx + 1, r, c - 1, board, word, visited);
        visited[r][c] = false; // backtrack
        return found;
    }
}

Approach 2

Level II: Optimized Backtracking (Frequency Pruning)

Intuition

Before starting DFS, check if the board contains enough characters to form the word.

Count the frequency of each char in the board and the word. If the board has fewer characters than the word for any char, return false immediately. This avoids $O(N \times M \times 3^L)$ work in impossible cases.

⏱ O(N * M + 3^L)💾 O(1) extra.

Detailed Dry Run

word="AAAAA", board has only two 'A's -> Return FALSE immediately.

N-Queens

The Constraint Logic

The N-Queens puzzle is about placing $N$ chess queens on an $N \times N$ chessboard so that no two queens threaten each other. A queen can attack in 3 ways: Row, Column, and Diagonal.

Efficient Collision Detection

Instead of checking every cell on the board (which is $O(N)$ ), we can use boolean arrays to mark occupied lanes:

Column: Index c
Main Diagonal: Index r - c (constant along the diagonal)
Anti-Diagonal: Index r + c (constant along the diagonal)

Place N queens on an N x N board without conflicts. Includes visual 4-Queens solution.

Hard

Examples

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Approach 1

Level I: Backtracking with Validation Function

Intuition

Place queens row by row. For each valid column in a row, move to the next row.

For each row r, try placing a queen at (r, c) where c from $0$ to $N-1$ . Check if (r, c) is safe by scanning all previously placed queens.

⏱ O(N!)💾 O(N^2) to store the board.

Detailed Dry Run

Dry Run: N=4
| Row | Action           | Collision Check |
| :-- | :--------------- | :-------------- |
| 0   | Place (0,0)      | Valid           |
| 1   | Try (1,0), (1,1) | ❌ Col/Diag     |
| 1   | Place (1,2)      | Valid           |
| 2   | Try (2,0)..(2,3) | ❌ ALL COLLIDE  |
| 1   | Backtrack (1,2)  | Try (1,3)...    |

java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
        List<List<String>> res = new ArrayList<>();
        backtrack(0, board, res);
        return res;
    }
    private void backtrack(int r, char[][] board, List<List<String>> res) {
        if (r == board.length) {
            res.add(construct(board));
            return;
        }
        for (int c = 0; c < board.length; c++) {
            if (isSafe(r, c, board)) {
                board[r][c] = 'Q';
                backtrack(r + 1, board, res);
                board[r][c] = '.';
            }
        }
    }
    private boolean isSafe(int r, int c, char[][] board) {
        for (int i = 0; i < r; i++) {
            for (int k = 0; k < board.length; k++) {
                if (board[i][k] == 'Q' && (k == c || Math.abs(r-i) == Math.abs(c-k))) return false;
            }
        }
        return true;
    }
    private List<String> construct(char[][] board) {
        List<String> path = new ArrayList<>();
        for (int i = 0; i < board.length; i++) path.add(new String(board[i]));
        return path;
    }
}

Approach 2

Level II: Optimized Backtracking (Hashing O(1) Checks)

Intuition

Use boolean arrays/sets to track occupied columns and diagonals for immediate collision detection.

Maintain cols, diag1 ( $r-c$ ), and diag2 ( $r+c$ ) sets. Before placing a queen at $(r, c)$ , check if $c$ , $r-c$ , or $r+c$ are in the sets.

⏱ O(N!)💾 O(N) to store sets.

Detailed Dry Run

Place (0,0): cols={0}, d1={0}, d2={0} Row 1: (1,1) fails (d1), (1,2) ok (c=2, d1=-1, d2=3).

java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), board, res);
        return res;
    }
    private void backtrack(int r, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, char[][] board, List<List<String>> res) {
        if (r == board.length) {
            List<String> sol = new ArrayList<>();
            for (char[] row : board) sol.add(new String(row));
            res.add(sol); return;
        }
        for (int c = 0; c < board.length; c++) {
            if (cols.contains(c) || d1.contains(r - c) || d2.contains(r + c)) continue;
            board[r][c] = 'Q';
            cols.add(c); d1.add(r - c); d2.add(r + c);
            backtrack(r + 1, cols, d1, d2, board, res);
            board[r][c] = '.';
            cols.remove(c); d1.remove(r - c); d2.remove(r + c);
        }
    }
}

Approach 3

Level III: Bit Manipulation (Ultimate Speed)

Intuition

Use integers as bitmasks to represent occupied columns and diagonals. This is the fastest way because bitwise operations are extremely cheap.

Let cols, ld (left-diagonal), and rd (right-diagonal) be integers. For each row, the available slots are ~(cols | ld | rd) & mask. Placing a queen update masks: cols | p, (ld | p) << 1, (rd | p) >> 1.

⏱ O(N!)💾 O(N)

Detailed Dry Run

N=4, mask=1111 Row 0: Try p=0001. New cols=0001, ld=0010, rd=0000 Row 1: Try p=0100...

Combinations

Choosing K from N

This is a classic $nCr$ problem. The goal is to choose $K$ elements from the set $\{1, 2, ..., N\}$ . Unlike permutations, the order doesn't matter.

Efficient Search

To avoid duplicate combinations like [1, 2] and [2, 1], we always choose numbers in increasing order. This means after choosing $i$ , the next number must be from $\{i+1, ..., N\}$ .

Pruning Optimization

If the number of remaining elements in the set is less than the number of elements we still need to pick, we can backtrack early.

Choose K numbers from 1 to N. Includes visual increasing-order tree.

Medium

Examples

Input: n = 4, k = 2
Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

Approach 1

Level I: Recursive Backtracking (Include/Exclude)

Intuition

For each number from 1 to $N$ , we either include it in our current combination or skip it.

At index $i$ , we either add $i$ to our list and call dfs(i + 1, count + 1), or we don't add $i$ and call dfs(i + 1, count). If count == k, we found a solution.

⏱ O(k * C(N, k))💾 O(k) for recursion stack.

Detailed Dry Run

Dry Run: n=3, k=2
| Start | Path | Action             | Next State |
| :---- | :--- | :----------------- | :--------- |
| 1     | []   | Choose 1, dfs(2)   | [1]        |
| 2     | [1]  | Choose 2, RES:[1,2]| -          |
| 2     | [1]  | Backtrack, try 3   | [1,3]      |
| 3     | [1]  | Choose 3, RES:[1,3]| -          |
| 1     | []   | Skip 1, try Choose 2| [2]        |

java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> res) {
        if (current.size() == k) {
            res.add(new ArrayList<>(current));
            return;
        }
        if (start > n) return;
        
        // Include
        current.add(start);
        backtrack(start + 1, n, k, current, res);
        current.remove(current.size() - 1);
        
        // Exclude
        backtrack(start + 1, n, k, current, res);
    }
}

Approach 2

Level II: Optimized Backtracking (Loop-based Pruning)

Intuition

Instead of binary choice, use a loop to pick the next element. Only iterate through elements that could possibly complete a combination of size $K$ .

The current number $i$ can go up to $N - (K - current.size()) + 1$ . Beyond that, there aren't enough numbers left to reach size $K$ .

⏱ O(k * C(N, k))💾 O(k)

Detailed Dry Run

n=4, k=3

At root, i can only go up to $4 - 3 + 1 = 2$ . So we only try picking 1 or 2 as the first element.

java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> res) {
        if (current.size() == k) {
            res.add(new ArrayList<>(current));
            return;
        }
        // Pruning: i <= n - (k - current.size()) + 1
        for (int i = start; i <= n - (k - current.size()) + 1; i++) {
            current.add(i);
            backtrack(i + 1, n, k, current, res);
            current.remove(current.size() - 1);
        }
    }
}

Sudoku Solver

The Sudoku Logic

Sudoku is a constraint satisfaction problem. A valid solution must have the digits 1-9 exactly once in every row, column, and $3 \times 3$ subgrid.

Backtracking Search

We find an empty cell, try placing a digit from 1-9, and if it's valid, move to the next empty cell. If no digit works, we backtrack to the previous cell and try the next possible digit.

State Representation

Instead of searching the board to validate, we can use boolean matrices or bitmasks to track which numbers are present in each row, column, and box.

Solve a Sudoku puzzle using backtracking. Includes visual constraint check trace.

Hard

Examples

Input: board = [[5,3,.,.,7,.,.,.,.],...]
Output: [[5,3,4,6,7,8,9,1,2],...]

Approach 1

Level I: Basic Backtracking

Intuition

Try every number in every empty cell.

Iterate through cells. For each '.', try numbers 1-9. Check if the number is valid in the current row, column, and $3 \times 3$ box by scanning the board.

⏱ O(9^{81}) in worst case, though much less in practice.💾 O(1) extra space beyond the board.

Detailed Dry Run

Dry Run Trace:
| Cell  | Value | Validity Check (R, C, B) | Action |
| :---: | :---: | :----------------------- | :----- |
| (0,2) | '4'   | [✔, ✔, ✔]                | Recurse|
| (0,3) | '1'   | [❌ Row Conflict]         | Try 2  |
| (0,3) | '6'   | [✔, ✔, ✔]                | Recurse|

java

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false;
            if (board[row][i] == c) return false;
            if (board[3*(row/3) + i/3][3*(col/3) + i%3] == c) return false;
        }
        return true;
    }
}

Approach 2

Level II: Optimized Backtracking (State Tracking with Bitmasks)

Intuition

Use bitmasks to mark digits used in rows, columns, and boxes for $O(1)$ validation.

Maintain rows[9], cols[9], and boxes[9] as integers. rows[i] & (1 << digit) tells us if digit is already in row i. This replaces the $O(9)$ isValid check with bitwise $O(1)$ .

⏱ O(9!^9)💾 O(1) (fixed number of integers).

Detailed Dry Run

To check if '5' can be placed at (0, 2): Check: (rows[0] | cols[2] | boxes[0]) & (1 << 5) == 0.

java

class Solution {
    int[] rows = new int[9], cols = new int[9], boxes = new int[9];
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int d = board[i][j] - '1';
                    flip(i, j, d);
                }
            }
        }
        solve(board, 0, 0);
    }
    private boolean solve(char[][] board, int r, int c) {
        if (c == 9) return solve(board, r + 1, 0);
        if (r == 9) return true;
        if (board[r][c] != '.') return solve(board, r, c + 1);
        
        int mask = ~(rows[r] | cols[c] | boxes[(r/3)*3 + c/3]) & 0x1FF;
        for (int d = 0; d < 9; d++) {
            if ((mask & (1 << d)) != 0) {
                flip(r, c, d);
                board[r][c] = (char)('1' + d);
                if (solve(board, r, c + 1)) return true;
                board[r][c] = '.';
                flip(r, c, d);
            }
        }
        return false;
    }
    private void flip(int r, int c, int d) {
        rows[r] ^= (1 << d);
        cols[c] ^= (1 << d);
        boxes[(r/3)*3 + c/3] ^= (1 << d);
    }
}

Palindrome Partitioning

Partitioning Strategy

A string can be partitioned in many ways. For Palindrome Partitioning, we only care about partitions where every substring is a palindrome.

The Decision Tree

At each step, we pick a substring s[start:end]. If it's a palindrome, we recurse on the remaining string s[end:].

Optimization with DP

Checking if a substring is a palindrome repeatedly is $O(N)$ . We can precompute a 2D boolean array isPalindrome[i][j] using Dynamic Programming in $O(N^2)$ to make each check $O(1)$ .

Partition a string into all possible palindromic substrings. Includes visual cut-tree.

Medium

Examples

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Approach 1

Level I: Standard Backtracking

Intuition

Try all possible prefixes. If a prefix is a palindrome, recurse on the suffix.

Iterate through the string. At each position, try taking a substring from the start to the current position. If it's a palindrome, add it to the path and recurse.

⏱ O(N * 2^N)💾 O(N)

Detailed Dry Run

Dry Run: s="aab"
| Start | Substr | Is Pal? | Path       | Action |
| :---- | :----- | :------ | :---       | :---   |
| 0     | "a"    | YES     | ["a"]      | DFS(1) |
| 1     | "a"    | YES     | ["a","a"]  | DFS(2) |
| 2     | "b"    | YES     | ["a","a","b"]| RES!! |
| 0     | "aa"   | YES     | ["aa"]     | DFS(2) |
| 2     | "b"    | YES     | ["aa","b"] | RES!!  |

java

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(0, s, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, String s, List<String> current, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                current.add(s.substring(start, i + 1));
                backtrack(i + 1, s, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) return false;
        }
        return true;
    }
}

Approach 2

Level II: Backtracking with DP Precomputation

Intuition

Avoid repetitive palindrome checks by precomputing all possible palindromes in the string.

Create a 2D boolean array dp[i][j] where dp[i][j] is true if s[i:j+1] is a palindrome. Use the recurrence: dp[i][j] = (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])).

⏱ O(2^N)💾 O(N^2)

Detailed Dry Run

s="aab" dp[0][0]=T, dp[1][1]=T, dp[2][2]=T dp[0][1] = (s[0]==s[1]) = T dp[1][2] = (s[1]==s[2]) = F dp[0][2] = (s[0]==s[2] && dp[1][1]) = F

java

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
        List<List<String>> res = new ArrayList<>();
        backtrack(0, s, dp, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, String s, boolean[][] dp, List<String> current, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (dp[start][i]) {
                current.add(s.substring(start, i + 1));
                backtrack(i + 1, s, dp, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
}

N-Queens II

Counting Solutions

This is identical to N-Queens I, but instead of returning the board layouts, we only need to return the total number of distinct solutions.

Optimization

Since we don't need to construct the board, we can use bitmasks for extremely fast collision detection and state management.

Count the number of distinct N-Queens solutions. Includes visual N=4 solution count.

Hard

Examples

Input: n = 4
Output: 2

Approach 1

Level I: Backtracking (Count only)

Intuition

Use the same backtracking logic as N-Queens I, but increment a counter instead of saving the board.

Maintain a count variable. Use boolean arrays to track occupied columns, main diagonals, and anti-diagonals.

⏱ O(N!)💾 O(N)

Detailed Dry Run

Dry Run: N=4
| Row | Valid Cols | Action | Count |
| :-- | :---       | :---   | :---  |
| 0   | {0,1,2,3}  | Try 1  | 0     |
| 1   | {3}        | Try 3  | 0     |
| 2   | {0}        | Try 0  | 0     |
| 3   | {2}        | FOUND! | 1     |

java

class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];
        boolean[] d1 = new boolean[2 * n];
        boolean[] d2 = new boolean[2 * n];
        backtrack(0, n, cols, d1, d2);
        return count;
    }
    private void backtrack(int r, int n, boolean[] cols, boolean[] d1, boolean[] d2) {
        if (r == n) {
            count++; return;
        }
        for (int c = 0; c < n; c++) {
            int id1 = r - c + n;
            int id2 = r + c;
            if (cols[c] || d1[id1] || d2[id2]) continue;
            cols[c] = d1[id1] = d2[id2] = true;
            backtrack(r + 1, n, cols, d1, d2);
            cols[c] = d1[id1] = d2[id2] = false;
        }
    }
}

Approach 2

Level II: Bitmask Backtracking

Intuition

Use integers as bitmasks for lightning-fast state management.

Represent occupied columns, diagonals as bits in an integer. Only use bitwise operations to check and update state.

⏱ O(N!)💾 O(N)

Detailed Dry Run

N=4. Initial: columns=0, ld=0, rd=0. Available: bits in ~(cols | ld | rd).

Regular Expression Matching

The Matching Logic

Implement regular expression matching with support for '.' and '*'.

'.' matches any single character.
'*' matches zero or more of the preceding element.

The Star (*) Dilemma

The '' is the most complex part of this problem. When we encounter a '', we have two choices:

Zero match: Skip the preceding element and the '*' (e.g., a* matches empty string).
One or more match: If the current character matches the preceding element, we consume one character of the string and stay at the same position in the pattern to potentially match more.

Implement regex matching with support for '.' and '*'. Includes visual state-space analysis.

Hard

Examples

Input: s = "aa", p = "a*"
Output: true

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Approach 1

Level I: Recursive Backtracking (Naive)

Intuition

Handle the base match, then branch for the '*' character.

For each call, check if the first character matches. If the second character of the pattern is '*', branch into 'skip' or 'consume' cases.

⏱ O((S+P) * 2^{S+P/2})💾 O(S^2 + P^2)

Detailed Dry Run

s="aa", p="a*"
| Step | s | p | First Match? | Action |
| :--- | :--- | :--- | :--- | :--- |
| 1 | "aa" | "a*" | YES | '*' detected, split |
| 2.1 | "aa" | "" | NO | Skip branch FAIL |
| 2.2 | "a" | "a*" | YES | Consume branch, recurse |
| 3.1 | "" | "a*" | YES | Consume branch, RES: true |

java

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        boolean firstMatch = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

        if (p.length() >= 2 && p.charAt(1) == '*') {
            return (isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p)));
        } else {
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }
}

Approach 2

Level II: Top-Down Memoization

Intuition

Cache results of (i, j) pairs where i is index in s and j is index in p.

The naive recursion has overlapping subproblems. By storing results in a 2D array/hashmap, we reduce complexity to $O(S imes P)$ .

⏱ O(S * P)💾 O(S * P)

Detailed Dry Run

Cache entries for s="aa", p="a*":
(0, 0) -> calls (0, 2) and (1, 0)
(0, 2) -> true (base case)
(1, 0) -> calls (1, 2) and (2, 0)
... all stored in memo table.

java

class Solution {
    public boolean isMatch(String s, String p) {
        Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
        return dp(0, 0, s, p, memo);
    }
    private boolean dp(int i, int j, String s, String p, Boolean[][] memo) {
        if (memo[i][j] != null) return memo[i][j];
        boolean res;
        if (j == p.length()) {
            res = i == s.length();
        } else {
            boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                res = dp(i, j + 2, s, p, memo) || (first && dp(i + 1, j, s, p, memo));
            } else {
                res = first && dp(i + 1, j + 1, s, p, memo);
            }
        }
        return memo[i][j] = res;
    }
}

Approach 3

Level III: Bottom-Up Dynamic Programming

Intuition

Build a table dp[i][j] where dp[i][j] is true if s[i:] matches p[j:].

Initialize dp[len(s)][len(p)] = true. Fill the table backwards from the base case.

⏱ O(S * P)💾 O(S * P)

Detailed Dry Run

DP Table for s="aa", p="a*":
|   | a | * | (end) |
|---|---|---|-------|
| a | T | T | F |
| a | T | T | F |
|(e)| F | T | T |

java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[m][n] = true;

        for (int i = m; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                boolean first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                if (j + 1 < n && p.charAt(j + 1) == '*') {
                    dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
                } else {
                    dp[i][j] = first && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}

Wildcard Matching

Matching Rules

'?' matches any single character.
'*' matches any sequence of characters (including empty sequence).

The Greedy '*' Logic

Unlike Regular Expression matching where a* depends on 'a', the Wildcard * is independent. It can match anything. This makes it a great candidate for greedy search or dynamic programming.

Implement wildcard pattern matching with support for '?' and '*'. Includes visual matching trace.

Hard

Examples

Input: s = "aa", p = "*"
Output: true

Input: s = "cb", p = "?a"
Output: false

Approach 1

Level I: Recursive Backtracking (Naive)

Intuition

Traverse both strings. If we hit '?', match one. If we hit '*', try matching zero or more characters.

Standard recursion with branching on '*'. This is $O(2^N)$ in the worst case (e.g., s="aaaaa", p="*a*a*a").

⏱ O(2^N)💾 O(N)

Detailed Dry Run

s="aa", p="*"
| Step | s | p | Action |
| :--- | :--- | :--- | :--- |
| 1 | "aa" | "*" | '*' detected, branch |
| 2.1 | "aa" | "" | FAIL (skip *) |
| 2.2 | "a" | "*" | RECURSE (consume 'a') |
| 3.1 | "a" | "" | FAIL (skip *) |
| 3.2 | "" | "*" | SUCCESS (consume 'a', match empty) |

java

class Solution {
    public boolean isMatch(String s, String p) {
        return backtrack(s, p, 0, 0);
    }
    private boolean backtrack(String s, String p, int i, int j) {
        if (j == p.length()) return i == s.length();
        if (p.charAt(j) == '*') {
            return backtrack(s, p, i, j + 1) || (i < s.length() && backtrack(s, p, i + 1, j));
        }
        if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            return backtrack(s, p, i + 1, j + 1);
        }
        return false;
    }
}

Approach 2

Level II: Top-Down Memoization

Intuition

Overlap in recursive branches for '*' leads to redundant work.

Store (i, j) match results to achieve $O(S imes P)$ complexity.

⏱ O(S * P)💾 O(S * P)

Detailed Dry Run

For s="abc", p="*c":
memo[0][0] calls memo[0][1] and memo[1][0].
memo[1][0] calls memo[1][1] and memo[2][0].
Redundant paths like (*, c) matching 'bc' are cached.

java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        Boolean[][] memo = new Boolean[m + 1][n + 1];
        return dp(0, 0, s, p, memo);
    }
    private boolean dp(int i, int j, String s, String p, Boolean[][] memo) {
        if (j == p.length()) return i == s.length();
        if (memo[i][j] != null) return memo[i][j];
        
        boolean res;
        if (p.charAt(j) == '*') {
            res = dp(i, j+1, s, p, memo) || (i < s.length() && dp(i+1, j, s, p, memo));
        } else if (i < s.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            res = dp(i+1, j+1, s, p, memo);
        } else {
            res = false;
        }
        return memo[i][j] = res;
    }
}

Approach 3

Level III: Optimized Greedy Path (Pointers)

Intuition

Instead of a full DP table, we can track the last '*' position and backtrack only as much as needed.

When we hit '', record the current s and p indices. If we hit a mismatch later, reset p to right after '', and s to one char after the previous recorded s index.

⏱ O(S * P) worst case, O(S) average.💾 O(1) extra.

Detailed Dry Run

s="adceb", p="*a*b"
p[0]='*', star_idx=0, s_tmp=0. p moves to 1.
s[0]='a', p[1]='a'. Match! i=1, j=2.
p[2]='*', star_idx=2, s_tmp=1. p moves to 3.
s[1]='d', p[3]='b'. Mismatch! Backtrack to star_idx=2, s_tmp=2.
Keep trying until s[4]='b', p[3]='b'. MATCH!

java

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0, starIdx = -1, sTmp = -1;
        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++; j++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                starIdx = j;
                sTmp = i;
                j++;
            } else if (starIdx != -1) {
                j = starIdx + 1;
                i = ++sTmp;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') j++;
        return j == p.length();
    }
}

Partition to K Equal Sum Subsets

Filling the Buckets

We need to divide $N$ numbers into $K$ groups, where each group has the same sum. This target sum is TotalSum / K.

Pruning Strategies (Crucial for Hard)

If TotalSum is not divisible by $K$ , return False immediately.
Sort nums in descending order to fill buckets with larger numbers first (fails faster on impossible branches).
If a bucket cannot take the current number and it's the first number in the bucket, skip because further search will fail too.

Partition an array into K subsets of equal sum. Includes visual bucket-filling trace.

Hard

Examples

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true

Approach 1

Level I: Backtracking (Optimized with Sorting)

Intuition

Try putting each number into each of the K buckets.

To optimize, we sort descending. In each step, we iterate through K buckets. If bucket[j] + nums[idx] <= target, we add it and recurse. If we hit the end, success.

⏱ O(K^N)💾 O(N)

Detailed Dry Run

nums=[5,4,3,2,1], target=5, k=3
Pick 5: Add to B1 (5). OK.
Pick 4: Add to B2 (4). OK.
Pick 3: B1(8)>5 (❌), B2(7)>5 (❌), B3(3). OK.
Pick 2: B1(5) (❌ skip), B2(6) (❌), B3(5). OK.

java

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums);
        int[] buckets = new int[k];
        return backtrack(nums.length - 1, nums, buckets, target);
    }
    private boolean backtrack(int idx, int[] nums, int[] buckets, int target) {
        if (idx == -1) return true;
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] + nums[idx] <= target) {
                buckets[i] += nums[idx];
                if (backtrack(idx - 1, nums, buckets, target)) return true;
                buckets[i] -= nums[idx];
            }
            if (buckets[i] == 0) break; // Pruning: first time bucket empty
        }
        return false;
    }
}

Geometric Constraint

To form a square, we must partition the matchsticks into 4 groups of equal length. This length must be TotalLength / 4.

Relation to K-Partition

This is a special case of Partition to K Equal Sum Subsets where $K=4$ . The same pruning strategies (descending sort, skip empty buckets) apply here for efficiency.

Performance at Scale

While basic backtracking works for $9 \times 9$ Sudoku, larger puzzles or high-volume solvers require better state management.

Bitmask Optimization

Instead of checking rows and columns using loops ( $O(N)$ ), we use a single bitmask for each row, column, and box. Checking for a conflict becomes a single bitwise AND operation ( $O(1)$ ).

Remove Invalid Parentheses

Minimal Removal

To make a string valid with minimal removals, we first calculate the number of misplaced open ( and closed ) parentheses.

BFS vs. Backtracking

BFS: Guarantees finding the minimal removal level first. We remove one paren at a time and check validity.
Backtracking: More memory efficient. We use the pre-calculated remOpen and remClosed to limit our search space and prune invalid branches early.

Remove the minimum number of invalid parentheses to make the input string valid. Includes visual removal tree.

Hard

Examples

Input: s = "()())()"
Output: ["(())()","()()()"]

Approach 1

Level I: Backtracking with Pruning

Intuition

Count how many '(' and ')' need to be removed, then use DFS to try all removal combinations.

Calculate remL and remR. In DFS, for each character: 1. If it's '(' and remL > 0, try removing it. 2. If it's ')' and remR > 0, try removing it. 3. Always try keeping it if valid.

⏱ O(2^N)💾 O(N)

Detailed Dry Run

s="())", remL=0, remR=1
1. Index 0 '(': Keep it. (L=1, R=0)
2. Index 1 ')': 
   - Remove: DFS(idx 2, L=1, R=0) -> "()" Valid!
   - Keep: (L=1, R=1)
3. Index 2 ')': 
   - Remove: DFS(idx 3, L=1, R=1) -> "()" Valid!

java

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int remL = 0, remR = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') remL++;
            else if (c == ')') {
                if (remL > 0) remL--;
                else remR++;
            }
        }
        Set<String> res = new HashSet<>();
        backtrack(s, 0, 0, 0, remL, remR, new StringBuilder(), res);
        return new ArrayList<>(res);
    }
    private void backtrack(String s, int idx, int leftCount, int rightCount, int remL, int remR, StringBuilder path, Set<String> res) {
        if (idx == s.length()) {
            if (remL == 0 && remR == 0) res.add(path.toString());
            return;
        }
        char c = s.charAt(idx);
        int len = path.length();
        if (c == '(' && remL > 0) backtrack(s, idx + 1, leftCount, rightCount, remL - 1, remR, path, res);
        if (c == ')' && remR > 0) backtrack(s, idx + 1, leftCount, rightCount, remL, remR - 1, path, res);
        
        path.append(c);
        if (c != '(' && c != ')') backtrack(s, idx + 1, leftCount, rightCount, remL, remR, path, res);
        else if (c == '(') backtrack(s, idx + 1, leftCount + 1, rightCount, remL, remR, path, res);
        else if (leftCount > rightCount) backtrack(s, idx + 1, leftCount, rightCount + 1, remL, remR, path, res);
        path.setLength(len);
    }
}

Beautiful Arrangement

The divisibility Rule

An arrangement is beautiful if for every position $i$ (1-indexed):

perm[i] % i == 0 OR
i % perm[i] == 0

Pruning in Backtracking

Instead of generating all $N!$ permutations and checking them, we check the condition at each step. If a number cannot be placed at the current index, we prune the entire branch.

Count the number of beautiful arrangements of numbers 1 to N. Includes visual placement trace.

Medium

Examples

Input: n = 2
Output: 2

Approach 1

Level I: Backtracking with Pruning

Intuition

Try placing each available number in the current position, checking the rule.

Use a visited array to track used numbers. At each position idx, iterate from 1 to N. If i is not used and satisfies the beautiful rule, place it and recurse.

⏱ O(K) where K is the number of valid permutations.💾 O(N)

Detailed Dry Run

N=3
Pos 1: Try 1 (1%1==0). OK.
Pos 2: Try 2 (2%2==0). OK.
Pos 3: Try 3 (3%3==0). OK. (Result=1)
Pos 2: Try 3 (3%2!=0, 2%3!=0). Fail.

java

class Solution {
    int count = 0;
    public int countArrangement(int n) {
        boolean[] visited = new boolean[n + 1];
        backtrack(n, 1, visited);
        return count;
    }
    private void backtrack(int n, int pos, boolean[] visited) {
        if (pos > n) {
            count++; return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
                visited[i] = true;
                backtrack(n, pos + 1, visited);
                visited[i] = false;
            }
        }
    }
}

Unique Paths III

The Grid Coverage Problem

Find the number of paths from the starting square to the ending square that walk over every non-obstacle square exactly once.

Backtracking with Path Counting

Count the total number of empty squares ( $N$ ).
DFS from the start, marking cells as visited (-1).
If we reach the end and our current path length equals $N+1$ (including the target), we found a valid path.

Find the number of paths in a grid that visit every empty square exactly once. Includes visual grid-coverage trace.

Hard

Examples

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2

Approach 1

Level I: Backtracking (DFS)

Intuition

Try all possible paths from start to end, counting steps taken.

Iterate through the grid to find the start and count empty cells. DFS in 4 directions. If we reach '2' and steps == totalEmpty, increment count.

⏱ O(3^{M * N})💾 O(M * N)

Detailed Dry Run

Trace for 1x3: [1, 0, 2]
Start at (0,0), empty=2.
Move to (0,1), steps=1. Mark visited.
Move to (0,2), steps=2. Target reached! Count++

java

class Solution {
    int res = 0, empty = 1, startX, startY;
    public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) empty++;
                else if (grid[i][j] == 1) {
                    startX = i; startY = j;
                }
            }
        }
        dfs(grid, startX, startY, 0);
        return res;
    }
    public void dfs(int[][] grid, int x, int y, int count) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) return;
        if (grid[x][y] == 2) {
            if (count == empty) res++;
            return;
        }
        grid[x][y] = -1;
        dfs(grid, x + 1, y, count + 1);
        dfs(grid, x - 1, y, count + 1);
        dfs(grid, x, y + 1, count + 1);
        dfs(grid, x, y - 1, count + 1);
        grid[x][y] = 0;
    }
}

Hamiltonian Path

Visiting All Vertices

A Hamiltonian Path is a path in an undirected or directed graph that visits every vertex exactly once.

The NP-Complete Challenge

This is a classic NP-complete problem. Unlike Eulerian paths (which visit every edge), there is no simple polynomial-time check for Hamiltonian paths.

Determine if a graph contains a path that visits every node exactly once. Includes visual node-visit trace.

Hard

Examples

Input: n=4, edges=[[0,1],[1,2],[2,3],[3,0]]
Output: true

Approach 1

Level I: Backtracking with Visited Set

Intuition

Pick a starting node and try to build a path of length N.

Try every node as a starting vertex. Perform DFS, keeping track of visited nodes. If the path length reaches $N$ , we found a Hamiltonian Path.

⏱ O(N!)💾 O(N)

Detailed Dry Run

N=3. Edges: 0-1, 1-2
1. Start at 0: Visit 0. Next: 1. Visit 1. Next: 2. Visit 2. Length=3. DONE!

java

class HamiltonianPath {
    public boolean hasPath(int n, int[][] adj) {
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (backtrack(i, 1, n, adj, visited)) return true;
        }
        return false;
    }
    private boolean backtrack(int u, int count, int n, int[][] adj, boolean[] visited) {
        if (count == n) return true;
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                if (backtrack(v, count + 1, n, adj, visited)) return true;
            }
        }
        visited[u] = false;
        return false;
    }
}

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.