Skip to content

12. Backtracking#

Theory#

Backtracking explores a decision tree: choose → explore → unchoose. Use it for combinatorial generation (permutations, subsets, combinations) and constraint satisfaction (N-Queens, Sudoku).

Template#

def backtrack(path, options):
    if complete(path):
        result.append(path[:])   # copy
        return
    for choice in options:
        if not valid(choice):
            continue
        path.append(choice)      # choose
        backtrack(path, next_options)  # explore
        path.pop()               # unchoose

Problem types#

Type State Examples
Subsets include / skip each element LC 78
Combinations start index to avoid duplicates LC 77, 39
Permutations used[] array or swap LC 46, 47
Grid search visited cells LC 79 Word Search

Pruning#

Cut branches early when partial state cannot lead to a valid solution — mention this to the interviewer (e.g. remaining count too small for target sum).

Complexity: often exponential; state clearly ("O(n!) permutations" / "O(2ⁿ) subsets"). See Recursion.

Problems at a glance#

LC Problem
46 Permutations ↗
77 Combinations ↗
78 Subsets ↗
784 Letter Case Permutation ↗
51 N-Queens ↗
37 Sudoku Solver ↗
79 Word Search ↗
416 Partition Equal Subset Sum ↗
39 Combination Sum ↗
131 Palindrome Partitioning ↗
40 Combination Sum II (avoid duplicates) ↗
47 Permutations II (handling duplicates) ↗
90 Subsets II ↗
93 Restore IP Addresses ↗
797 Find All Paths from Source to Destination ↗
22 Generate Parentheses ↗
140 Word Break II ↗
17 Letter Combinations of a Phone Number ↗

1. Basic Backtracking (Permutation, Combination, Subset Generation)#

Classic problems generating permutations, combinations, or subsets via recursion and backtracking.

Problem 1: Permutations (Leetcode:46)#

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True          # choose
                path.append(nums[i])
                backtrack()             # explore
                path.pop()              # unchoose
                used[i] = False

        backtrack()
        return result
Explanation:
At each level, pick one unused element:

  1. Base case: When path has all n elements, append a copy to result.
  2. Choose: Mark used[i], append nums[i] to path.
  3. Explore: Recurse to fill the next position.
  4. Unchoose: Pop and unmark so other branches can use nums[i].

Time: O(n × n!)  |  Space: O(n) recursion depth

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []

        def backtrack(start: int) -> None:
            if start == len(nums):
                result.append(nums[:])
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]  # choose
                backtrack(start + 1)                          # explore
                nums[start], nums[i] = nums[i], nums[start]  # unchoose

        backtrack(0)
        return result
Explanation:
Fix position start, then swap each candidate into that slot:

  1. Choose: Swap nums[start] with nums[i] to place nums[i] at position start.
  2. Explore: Recurse on start + 1.
  3. Unchoose: Swap back to restore the array before trying the next i.

Avoids a used[] array — the prefix [0..start) is fixed by swaps.

Time: O(n × n!)  |  Space: O(n) recursion depth

Problem 2: Combinations (Leetcode:77)#

Problem Statement

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= n
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            if len(path) == k:
                result.append(path[:])
                return
            for num in range(start, n + 1):
                path.append(num)        # choose
                backtrack(num + 1)      # explore (only larger nums)
                path.pop()              # unchoose

        backtrack(1)
        return result
Explanation:
Build combinations in increasing order so [1,2] and [2,1] are never both generated:

  1. Choose: Append num to path.
  2. Explore: Recurse from num + 1 (forward-only picks).
  3. Unchoose: Pop before trying the next candidate.

Time: O(k × C(n,k))  |  Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        queue: List[List[int]] = [[]]

        for num in range(1, n + 1):
            next_queue: List[List[int]] = []
            for combo in queue:
                if len(combo) < k:
                    next_queue.append(combo)              # skip num
                    next_queue.append(combo + [num])      # include num
            queue = next_queue

        return [c for c in queue if len(c) == k]
Explanation:
Process numbers 1..n one at a time. For each existing partial combination, branch into exclude num or include num. After all numbers, filter to length k. Same combinatorial space as recursion, but explicit queue instead of call stack.

Time: O(k × C(n,k))  |  Space: O(C(n,k))

Problem 3: Subsets (Leetcode:78)#

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            result.append(path[:])          # every path is a valid subset
            for i in range(start, len(nums)):
                path.append(nums[i])        # choose
                backtrack(i + 1)            # explore
                path.pop()                  # unchoose

        backtrack(0)
        return result
Explanation:
For each index, decide include or skip (skip = try next i without choosing current):

  1. Record: Every recursive call records the current path as a subset.
  2. Choose: Include nums[i], recurse from i + 1.
  3. Unchoose: Pop and try the next element.

Time: O(n × 2ⁿ)  |  Space: O(n)

1
2
3
4
5
6
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = [[]]
        for num in nums:
            result += [subset + [num] for subset in result]
        return result
Explanation:
For each new number, duplicate every existing subset and append num. Each element doubles the result count — equivalent to the include/exclude tree, but bottom-up.

Time: O(n × 2ⁿ)  |  Space: O(2ⁿ)

Problem 4: Letter Case Permutation (Leetcode:784)#

Problem Statement

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

Constraints:

  • 1 <= s.length <= 12
  • s consists of lowercase English letters, uppercase English letters, and digits.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        result: List[str] = []
        chars = list(s)

        def backtrack(index: int) -> None:
            if index == len(chars):
                result.append("".join(chars))
                return
            if chars[index].isalpha():
                chars[index] = chars[index].lower()  # choose lower
                backtrack(index + 1)                 # explore
                chars[index] = chars[index].upper()  # choose upper
                backtrack(index + 1)                 # explore
            else:
                backtrack(index + 1)                 # digit: no branch

        backtrack(0)
        return result
Explanation:
At each letter, branch into lowercase and uppercase; digits have a single path:

  1. Choose: Set the character case (or leave digit unchanged).
  2. Explore: Move to index + 1.
  3. Unchoose: Implicit — the next branch overwrites the case at this index.

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

1
2
3
4
5
6
7
8
9
class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        result = [""]
        for ch in s:
            if ch.isalpha():
                result = [r + ch.lower() for r in result] + [r + ch.upper() for r in result]
            else:
                result = [r + ch for r in result]
        return result
Explanation:
Build strings left to right. Each letter doubles the result set (lower + upper branches). Digits extend every string by one character. Same decision tree, explored breadth-first.

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

2. Backtracking with Constraints (N-Queens, Sudoku, Graph Coloring)#

Backtracking with added constraints to prune search space.

Problem 1: N-Queens (Leetcode:51)#

Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order**.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:


Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

  • 1 <= n <= 9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result: List[List[str]] = []
        cols: set[int] = set()
        diag1: set[int] = set()   # row + col
        diag2: set[int] = set()   # row - col
        board = [["."] * n for _ in range(n)]

        def backtrack(row: int) -> None:
            if row == n:
                result.append(["".join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row + col) in diag1 or (row - col) in diag2:
                    continue
                cols.add(col); diag1.add(row + col); diag2.add(row - col)  # choose
                board[row][col] = "Q"
                backtrack(row + 1)                                          # explore
                board[row][col] = "."                                       # unchoose
                cols.remove(col); diag1.remove(row + col); diag2.remove(row - col)

        backtrack(0)
        return result
Explanation:
Place one queen per row. Track occupied columns and both diagonal directions:

  1. Prune: Skip columns that would be attacked.
  2. Choose: Mark constraints, place Q.
  3. Explore: Recurse to next row.
  4. Unchoose: Clear cell and release constraints.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result: List[List[str]] = []
        cols = diag1 = diag2 = 0
        queens = [-1] * n

        def backtrack(row: int) -> None:
            if row == n:
                board = []
                for r in range(n):
                    row_str = ["."] * n
                    row_str[queens[r]] = "Q"
                    board.append("".join(row_str))
                result.append(board)
                return
            for col in range(n):
                bit = 1 << col
                if cols & bit or diag1 & bit or diag2 & bit:
                    continue
                queens[row] = col
                cols |= bit; diag1 |= bit; diag2 |= bit       # choose
                backtrack(row + 1)                            # explore
                cols ^= bit; diag1 >>= 1; diag2 = (diag2 >> 1) | (1 << (n - 1))  # unchoose

        backtrack(0)
        return result
Explanation:
Same row-by-row logic, but columns/diagonals are bitmasks — O(1) conflict checks. diag1 shifts right each row; diag2 shifts left and wraps.

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

Problem 2: Sudoku Solver (Leetcode:37)#

Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:


Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        empty: List[tuple[int, int]] = []

        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val == ".":
                    empty.append((r, c))
                else:
                    rows[r].add(val)
                    cols[c].add(val)
                    boxes[(r // 3) * 3 + c // 3].add(val)

        def backtrack(index: int) -> bool:
            if index == len(empty):
                return True
            r, c = empty[index]
            box = (r // 3) * 3 + c // 3
            for digit in map(str, range(1, 10)):
                if digit in rows[r] or digit in cols[c] or digit in boxes[box]:
                    continue
                board[r][c] = digit
                rows[r].add(digit); cols[c].add(digit); boxes[box].add(digit)  # choose
                if backtrack(index + 1):                                      # explore
                    return True
                board[r][c] = "."
                rows[r].remove(digit); cols[c].remove(digit); boxes[box].remove(digit)  # unchoose
            return False

        backtrack(0)
Explanation:
Fill empty cells in fixed order. Precompute row/col/box used digits for O(1) validity:

  1. Choose: Place a valid digit, update constraint sets.
  2. Explore: Recurse to next empty cell.
  3. Unchoose: Reset cell and sets if no digit leads to a solution.

Time: O(9^m) where m = empty cells  |  Space: O(81)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        rows = cols = boxes = [0] * 9
        empty: List[tuple[int, int]] = []

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    empty.append((r, c))
                else:
                    bit = 1 << (int(board[r][c]) - 1)
                    b = (r // 3) * 3 + c // 3
                    rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit

        def backtrack(index: int) -> bool:
            if index == len(empty):
                return True
            r, c = empty[index]
            b = (r // 3) * 3 + c // 3
            used = rows[r] | cols[c] | boxes[b]
            for d in range(9):
                bit = 1 << d
                if used & bit:
                    continue
                board[r][c] = str(d + 1)
                rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit
                if backtrack(index + 1):
                    return True
                board[r][c] = "."
                rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            return False

        backtrack(0)
Explanation:
Each row/col/box stores a 9-bit mask of used digits. Available digits = bits not in used. Faster constant-time checks than set membership.

Time: O(9^m)  |  Space: O(81)

Problem 3: Graph Coloring Problem (GeeksforGeeks)#

Problem Statement

Given an undirected graph with V vertices (0-indexed) and M colors, assign a color to every vertex so that no two adjacent vertices share the same color. Return true if such a coloring exists, else false.

Example 1:

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0],[0,2]], M = 3
Output: true
Explanation: Colors [0,1,0,1] (or similar) work — no edge connects same-colored vertices.

Example 2:

Input: V = 3, edges = [[0,1],[1,2],[0,2]], M = 2
Output: false
Explanation: A triangle needs 3 colors with only 2 available.

Constraints:

  • 1 <= V <= 20
  • 1 <= M <= V
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def graph_coloring(V: int, edges: List[List[int]], M: int) -> bool:
    graph = [[] for _ in range(V)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    colors = [-1] * V

    def is_safe(vertex: int, color: int) -> bool:
        for neighbor in graph[vertex]:
            if colors[neighbor] == color:
                return False
        return True

    def backtrack(vertex: int) -> bool:
        if vertex == V:
            return True
        for color in range(M):
            if not is_safe(vertex, color):
                continue
            colors[vertex] = color       # choose
            if backtrack(vertex + 1):    # explore
                return True
            colors[vertex] = -1          # unchoose
        return False

    return backtrack(0)
Explanation:
Color vertices 0..V-1 in order:

  1. Prune: Skip colors that conflict with already-colored neighbors.
  2. Choose: Assign color to vertex.
  3. Explore: Recurse to next vertex.
  4. Unchoose: Reset to -1 before trying next color.

Time: O(M^V)  |  Space: O(V + E)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def graph_coloring(V: int, edges: List[List[int]], M: int) -> bool:
    adj_mask = [0] * V
    for u, v in edges:
        adj_mask[u] |= 1 << v
        adj_mask[v] |= 1 << u

    colors = [0] * V

    def backtrack(vertex: int) -> bool:
        if vertex == V:
            return True
        used = 0
        for neighbor in range(V):
            if adj_mask[vertex] & (1 << neighbor):
                used |= 1 << colors[neighbor]
        for color in range(M):
            if used & (1 << color):
                continue
            colors[vertex] = color
            if backtrack(vertex + 1):
                return True
        return False

    return backtrack(0)
Explanation:
Build a bitmask of neighbor colors already used — O(1) conflict check per color try. Same choose → explore → unchoose flow, tighter inner loop.

Time: O(M^V)  |  Space: O(V)

Problem 4: Word Search (Leetcode:79)#

Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:


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

Example 2:


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

Example 3:


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

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        def backtrack(r: int, c: int, index: int) -> bool:
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            if board[r][c] != word[index]:
                return False

            temp = board[r][c]
            board[r][c] = "#"                              # choose
            found = (
                backtrack(r + 1, c, index + 1) or
                backtrack(r - 1, c, index + 1) or
                backtrack(r, c + 1, index + 1) or
                backtrack(r, c - 1, index + 1)
            )                                              # explore
            board[r][c] = temp                             # unchoose
            return found

        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, 0):
                    return True
        return False
Explanation:
Try every cell as start. Match word[index], mark visited, explore 4 neighbors, restore:

  1. Choose: Mark cell #.
  2. Explore: DFS next character.
  3. Unchoose: Restore original letter.

Time: O(m × n × 4^L)  |  Space: O(L)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        visited = [[False] * cols for _ in range(rows)]

        def backtrack(r: int, c: int, index: int) -> bool:
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            if visited[r][c] or board[r][c] != word[index]:
                return False

            visited[r][c] = True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if backtrack(r + dr, c + dc, index + 1):
                    return True
            visited[r][c] = False
            return False

        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, 0):
                    return True
        return False
Explanation:
Same backtracking tree with explicit visited matrix instead of mutating the board. Clearer state restoration at the cost of O(m × n) extra space.

Time: O(m × n × 4^L)  |  Space: O(m × n + L)

3. Backtracking with Combinatorial Optimization (Subset Sum, Partition, Palindrome Partitioning)#

Problems where backtracking is used to explore subsets or partitions optimizing certain conditions.

Problem 1: Partition Equal Subset Sum (Leetcode:416)#

Problem Statement

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2

        def backtrack(start: int, curr_sum: int) -> bool:
            if curr_sum == target:
                return True
            if curr_sum > target:
                return False
            for i in range(start, len(nums)):
                if backtrack(i + 1, curr_sum + nums[i]):  # choose → explore
                    return True
            return False

        return backtrack(0, 0)
Explanation:
Find a subset summing to total / 2:

  1. Prune: Stop if curr_sum > target.
  2. Choose: Include nums[i], recurse from i + 1.
  3. Unchoose: Implicit — next loop iteration skips nums[i].

Time: O(2ⁿ)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        memo: dict[tuple[int, int], bool] = {}

        def backtrack(index: int, curr_sum: int) -> bool:
            if curr_sum == target:
                return True
            if curr_sum > target or index == len(nums):
                return False
            key = (index, curr_sum)
            if key in memo:
                return memo[key]
            memo[key] = (
                backtrack(index + 1, curr_sum + nums[index]) or
                backtrack(index + 1, curr_sum)
            )
            return memo[key]

        return backtrack(0, 0)
Explanation:
Same include/skip tree, but cache (index, curr_sum) to avoid recomputing identical subproblems. Still backtracking at its core — memo prunes repeated branches.

Time: O(n × target)  |  Space: O(n × target)

Problem 2: Combination Sum (Leetcode:39)#

Problem Statement

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

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    continue
                path.append(candidates[i])              # choose
                backtrack(i, remaining - candidates[i]) # explore (reuse allowed)
                path.pop()                              # unchoose

        backtrack(0, target)
        return result
Explanation:
Sorted implicitly by always picking from start onward — avoids duplicate orderings like [2,3] vs [3,2]:

  1. Choose: Add candidates[i] to path.
  2. Explore: Recurse from i (same element reusable).
  3. Unchoose: Pop before next candidate.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result: List[List[int]] = []
        stack: List[tuple[List[int], int, int]] = [([], 0, target)]  # path, start, remaining

        while stack:
            path, start, remaining = stack.pop()
            if remaining == 0:
                result.append(path)
                continue
            for i in range(start, len(candidates)):
                val = candidates[i]
                if val > remaining:
                    continue
                stack.append((path, i, remaining))           # skip
                stack.append((path + [val], i, remaining - val))  # include

        return result
Explanation:
Explicit stack simulates the recursion. Each frame branches into skip/include for every candidate from start. Same combinatorial tree, iterative control flow.

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

Problem 3: Palindrome Partitioning (Leetcode:131)#

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

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

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result: List[List[str]] = []
        path: List[str] = []

        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        def backtrack(start: int) -> None:
            if start == len(s):
                result.append(path[:])
                return
            for end in range(start, len(s)):
                if not is_palindrome(start, end):
                    continue
                path.append(s[start:end + 1])   # choose
                backtrack(end + 1)              # explore
                path.pop()                      # unchoose

        backtrack(0)
        return result
Explanation:
At each position, try every palindrome substring as the next partition piece:

  1. Prune: Skip non-palindrome substrings.
  2. Choose: Append substring to path.
  3. Explore: Recurse from end + 1.
  4. Unchoose: Pop before next end.

Time: O(n × 2ⁿ)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        palindrome = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                palindrome[i][j] = (s[i] == s[j]) and (j - i < 2 or palindrome[i + 1][j - 1])

        result: List[List[str]] = []
        path: List[str] = []

        def backtrack(start: int) -> None:
            if start == n:
                result.append(path[:])
                return
            for end in range(start, n):
                if not palindrome[start][end]:
                    continue
                path.append(s[start:end + 1])
                backtrack(end + 1)
                path.pop()

        backtrack(0)
        return result
Explanation:
Precompute palindrome[i][j] in O(n²) so each cut check is O(1). Backtracking tree is identical — preprocessing prunes the inner palindrome test.

Time: O(n² + n × 2ⁿ)  |  Space: O(n²)

Problem 4: Subset Sum (GeeksforGeeks)#

Problem Statement

Given a set of non-negative integers nums and a target sum, determine if any subset of nums sums to sum.

Example 1:

Input: nums = [3, 34, 4, 12, 5, 2], sum = 9
Output: true
Explanation: Subset {4, 5} sums to 9.

Example 2:

Input: nums = [3, 34, 4, 12, 5, 2], sum = 30
Output: false

Constraints:

  • 1 <= nums.length <= 200
  • 0 <= nums[i] <= 100
  • 0 <= sum <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def subset_sum(nums: List[int], target: int) -> bool:
    def backtrack(index: int, curr_sum: int) -> bool:
        if curr_sum == target:
            return True
        if index == len(nums) or curr_sum > target:
            return False
        return (
            backtrack(index + 1, curr_sum + nums[index]) or  # choose
            backtrack(index + 1, curr_sum)                   # skip
        )

    return backtrack(0, 0)
Explanation:
For each element, branch into include or exclude:

  1. Choose: Add nums[index] to running sum, recurse.
  2. Skip: Move to next index without adding.
  3. Base: Return true when sum equals target.

Time: O(2ⁿ)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def subset_sum(nums: List[int], target: int) -> bool:
    memo: dict[tuple[int, int], bool] = {}

    def backtrack(index: int, curr_sum: int) -> bool:
        if curr_sum == target:
            return True
        if index == len(nums) or curr_sum > target:
            return False
        key = (index, curr_sum)
        if key in memo:
            return memo[key]
        memo[key] = (
            backtrack(index + 1, curr_sum + nums[index]) or
            backtrack(index + 1, curr_sum)
        )
        return memo[key]

    return backtrack(0, 0)
Explanation:
Cache (index, curr_sum) to avoid revisiting the same subproblem. Still a backtracking decision tree — memoization prunes duplicate branches.

Time: O(n × target)  |  Space: O(n × target)

4. Backtracking with Pruning and Early Stopping#

Optimizing backtracking using pruning techniques like sorting, bounding, or memoization.

Problem 1: N-Queens with Pruning (Leetcode:51)#

Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order**.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:


Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

  • 1 <= n <= 9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result: List[List[str]] = []
        cols: set[int] = set()
        diag1: set[int] = set()
        diag2: set[int] = set()
        board = [["."] * n for _ in range(n)]

        def backtrack(row: int) -> None:
            if row == n:
                result.append(["".join(r) for r in board])
                return
            # prune: if remaining rows can't fit remaining cols, skip (implicit via conflict check)
            for col in range(n):
                d1, d2 = row + col, row - col
                if col in cols or d1 in diag1 or d2 in diag2:
                    continue
                cols.add(col); diag1.add(d1); diag2.add(d2)
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."
                cols.remove(col); diag1.remove(d1); diag2.remove(d2)

        backtrack(0)
        return result
Explanation:
Pruning happens before placing each queen — conflict sets reject entire columns instantly instead of exploring deep invalid branches. Choose → explore → unchoose with aggressive early cut-off.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result: List[List[str]] = []
        cols = diag1 = diag2 = 0
        queens = [-1] * n

        def backtrack(row: int) -> None:
            if row == n:
                result.append(
                    ["".join("Q" if queens[r] == c else "." for c in range(n)) for r in range(n)]
                )
                return
            available = ((1 << n) - 1) & ~cols & ~diag1 & ~diag2
            while available:
                bit = available & -available
                col = bit.bit_length() - 1
                queens[row] = col
                cols |= bit
                diag1 = (diag1 | bit) << 1
                diag2 = (diag2 | bit) >> 1
                backtrack(row + 1)
                cols ^= bit
                diag1 >>= 1
                diag2 = (diag2 >> 1) | (1 << (n - 1))
                available ^= bit

        backtrack(0)
        return result
Explanation:
available bitmask lists all non-conflicting columns in O(1). Iterate only valid columns — skips entire subtrees without per-column set lookups.

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

Problem 2: Word Search with Pruning (Leetcode:79)#

Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:


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

Example 2:


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

Example 3:


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

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])

        def backtrack(r: int, c: int, index: int) -> bool:
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            if board[r][c] != word[index]:   # prune immediately
                return False

            temp = board[r][c]
            board[r][c] = "#"
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if backtrack(r + dr, c + dc, index + 1):
                    return True
            board[r][c] = temp
            return False

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0] and backtrack(r, c, 0):  # prune starts
                    return True
        return False
Explanation:
Two pruning layers: only start from cells matching word[0], and return immediately on character mismatch before recursing. Cuts dead branches early in the choose → explore → unchoose tree.

Time: O(m × n × 4^L)  |  Space: O(L)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        root = TrieNode()
        node = root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

        rows, cols = len(board), len(board[0])

        def backtrack(r: int, c: int, trie_node: TrieNode) -> bool:
            ch = board[r][c]
            if ch == "#" or ch not in trie_node.children:
                return False
            next_node = trie_node.children[ch]
            if next_node.is_end:
                return True
            board[r][c] = "#"
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and backtrack(nr, nc, next_node):
                    return True
            board[r][c] = ch
            return False

        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, root):
                    return True
        return False
Explanation:
A trie over word prunes paths that don't match any prefix — useful when searching multiple words on the same board (LC 212). For a single word, behaves like Approach 1 with prefix validation.

Time: O(m × n × 4^L)  |  Space: O(L)

Problem 3: Combination Sum II (avoid duplicates) (Leetcode:40)#

Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

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

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                if candidates[i] > remaining:
                    break
                path.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i])
                path.pop()

        backtrack(0, target)
        return result
Explanation:
Sort first, then skip duplicate values at the same tree level (i > start check):

  1. Choose: Add candidates[i].
  2. Explore: Recurse from i + 1 (each element used once).
  3. Unchoose: Pop before next branch.
  4. Prune: Break when candidates[i] > remaining.

Time: O(2ⁿ)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(index: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path[:])
                return
            if index == len(candidates):
                return
            path.append(candidates[index])
            backtrack(index + 1, remaining - candidates[index])  # choose
            path.pop()                                           # unchoose
            while index + 1 < len(candidates) and candidates[index + 1] == candidates[index]:
                index += 1
            backtrack(index + 1, remaining)                      # skip duplicates

        backtrack(0, target)
        return result
Explanation:
Explicit choose/skip branches. After unchoosing, advance index past all equal values to avoid duplicate combinations. Same tree, different duplicate-skipping style.

Time: O(2ⁿ)  |  Space: O(n)

5. Backtracking on Grids / Maze Problems#

Exploring paths or all possible moves on grids, mazes, or board games.

Problem 1: Rat in a Maze (GeeksforGeeks)#

Problem Statement

Given an n × n binary matrix maze where 1 means open and 0 means blocked, find all paths for a rat from (0, 0) to (n-1, n-1). The rat can move down (D) or right (R) only.

Example 1:

Input: maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]
Output: ["DRDDRR", "DRDRR", "DDRR"]

Example 2:

Input: maze = [[1,0],[1,0]]
Output: []

Constraints:

  • 2 <= n <= 5
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def rat_in_maze(maze: List[List[int]]) -> List[str]:
    n = len(maze)
    result: List[str] = []
    path: List[str] = []

    def backtrack(r: int, c: int) -> None:
        if r == n - 1 and c == n - 1:
            result.append("".join(path))
            return
        for dr, dc, move in ((1, 0, "D"), (0, 1, "R")):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                maze[nr][nc] = 0
                path.append(move)
                backtrack(nr, nc)
                path.pop()
                maze[nr][nc] = 1

    if maze[0][0] == 1:
        maze[0][0] = 0
        backtrack(0, 0)
        maze[0][0] = 1
    return sorted(result)
Explanation:
DFS from start, try Down then Right. Mark cells visited: choose → explore → unchoose.

Time: O(2^(2n))  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def rat_in_maze(maze: List[List[int]]) -> List[str]:
    n = len(maze)
    result: List[str] = []
    path: List[str] = []
    visited = [[False] * n for _ in range(n)]

    def backtrack(r: int, c: int) -> None:
        if r == n - 1 and c == n - 1:
            result.append("".join(path))
            return
        for dr, dc, move in ((1, 0, "D"), (0, 1, "R")):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1 and not visited[nr][nc]:
                visited[nr][nc] = True
                path.append(move)
                backtrack(nr, nc)
                path.pop()
                visited[nr][nc] = False

    if maze[0][0] == 1:
        visited[0][0] = True
        backtrack(0, 0)
    return sorted(result)
Explanation:
Same tree with separate visited matrix — preserves original maze.

Time: O(2^(2n))  |  Space: O(n²)

Problem 2: Knight’s Tour Problem (GeeksforGeeks)#

Problem Statement

Given an n × n chessboard, find a sequence of knight moves that visits every cell exactly once starting from (0, 0).

Example 1:

Input: n = 5
Output: a 5×5 board with move numbers 1..25

Example 2:

Input: n = 3
Output: no solution

Constraints:

  • 1 <= n <= 8
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def knights_tour(n: int) -> List[List[int]] | None:
    board = [[0] * n for _ in range(n)]
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

    def onward(r: int, c: int) -> int:
        return sum(
            0 <= r + dr < n and 0 <= c + dc < n and board[r + dr][c + dc] == 0
            for dr, dc in moves
        )

    def backtrack(r: int, c: int, step: int) -> bool:
        if step == n * n:
            return True
        opts = []
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:
                opts.append((onward(nr, nc), nr, nc))
        for _, nr, nc in sorted(opts):
            board[nr][nc] = step + 1
            if backtrack(nr, nc, step + 1):
                return True
            board[nr][nc] = 0
        return False

    board[0][0] = 1
    return board if backtrack(0, 0, 1) else None
Explanation:
Sort moves by fewest onward options (Warnsdorff) to prune early. Choose → explore → unchoose on each cell placement.

Time: heavily pruned  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def knights_tour(n: int) -> List[List[int]] | None:
    board = [[0] * n for _ in range(n)]
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

    def backtrack(r: int, c: int, step: int) -> bool:
        if step == n * n:
            return True
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:
                board[nr][nc] = step + 1
                if backtrack(nr, nc, step + 1):
                    return True
                board[nr][nc] = 0
        return False

    board[0][0] = 1
    return board if backtrack(0, 0, 1) else None
Explanation:
Try all 8 knight moves at each step. Simpler but slower — good for small boards.

Time: O(8^(n²))  |  Space: O(n²)

6. Backtracking with State Restoration (Sudoku, Permutation with Duplicates)#

Backtracking problems where careful state restoration is key for correctness and efficiency.

Problem 1: Permutations II (handling duplicates) (Leetcode:47)#

Problem Statement

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: List[List[int]] = []
        path: List[int] = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(len(nums)):
                if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return result
Explanation:
Sort + skip duplicate values at same level when previous equal is unused. Choose → explore → unchoose with used[].

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: List[List[int]] = []

        def backtrack(start: int) -> None:
            if start == len(nums):
                result.append(nums[:])
                return
            seen = set()
            for i in range(start, len(nums)):
                if nums[i] in seen:
                    continue
                seen.add(nums[i])
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]

        backtrack(0)
        return result
Explanation:
At each position, swap in each unique value. seen set skips duplicate swaps at the same level.

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

Problem 2: Subsets II (Leetcode:90)#

Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: List[List[int]] = []
        path: List[int] = []

        def backtrack(start: int) -> None:
            result.append(path[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result
Explanation:
Sort, then skip duplicate values at the same recursion level. Choose → explore → unchoose.

Time: O(n × 2ⁿ)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: List[List[int]] = [[]]
        for num in nums:
            new = []
            for subset in result:
                if not new and subset and subset[-1] == num:
                    continue
                new.append(subset + [num])
            result.extend(new)
        return result
Explanation:
Iteratively extend subsets. Skip adding duplicate num to the same-sized subset twice in one pass.

Time: O(n × 2ⁿ)  |  Space: O(2ⁿ)

Problem 3: Restore IP Addresses (Leetcode:93)#

Problem Statement

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

Given a string s containing only digits, return all possible valid IP addresses by inserting dots into s.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

  • 1 <= s.length <= 20
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result: List[str] = []
        parts: List[str] = []

        def valid(segment: str) -> bool:
            return len(segment) <= 3 and (segment[0] != "0" or len(segment) == 1) and int(segment) <= 255

        def backtrack(start: int) -> None:
            if len(parts) == 4:
                if start == len(s):
                    result.append(".".join(parts))
                return
            for end in range(start + 1, min(start + 4, len(s) + 1)):
                segment = s[start:end]
                if not valid(segment):
                    continue
                parts.append(segment)
                backtrack(end)
                parts.pop()

        backtrack(0)
        return result
Explanation:
Build 4 segments left to right. Each segment is 1–3 digits, no leading zeros, value ≤ 255. Choose → explore → unchoose on parts.

Time: O(3⁴) = O(81)  |  Space: O(4)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result: List[str] = []
        n = len(s)

        def valid(segment: str) -> bool:
            return len(segment) <= 3 and (segment[0] != "0" or len(segment) == 1) and int(segment) <= 255

        for i in range(1, min(4, n)):
            for j in range(i + 1, min(i + 4, n)):
                for k in range(j + 1, min(j + 4, n)):
                    a, b, c, d = s[:i], s[i:j], s[j:k], s[k:]
                    if all(valid(seg) for seg in (a, b, c, d)):
                        result.append(f"{a}.{b}.{c}.{d}")
        return result
Explanation:
Enumerate all dot positions (3 cuts). Validate each of the 4 segments. Same search space as backtracking, flat iteration.

Time: O(1)  |  Space: O(1)

7. Backtracking with Bitmasking (Subset States, TSP)#

Using bitmasking to efficiently represent subsets or states during backtracking.

Problem 1: Traveling Salesman Problem (TSP) (GeeksforGeeks)#

Problem Statement

Given n cities and a cost matrix dist where dist[i][j] is travel cost from city i to j, find the minimum cost to visit every city exactly once and return to the start.

Example 1:

Input: dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
Output: 80
Explanation: Tour 0→1→3→2→0 costs 10+25+30+15 = 80.

Example 2:

Input: dist = [[0,20],[20,0]]
Output: 40

Constraints:

  • 2 <= n <= 15
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def tsp(dist: List[List[int]]) -> int:
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0

    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)) or dp[mask][u] == INF:
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                nmask = mask | (1 << v)
                dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + dist[u][v])

    full = (1 << n) - 1
    return min(dp[full][u] + dist[u][0] for u in range(1, n))
Explanation:
dp[mask][u] = min cost to reach u having visited cities in mask. Extend one city at a time — bitmask encodes the subset of visited cities.

Time: O(n² × 2ⁿ)  |  Space: O(n × 2ⁿ)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def tsp(dist: List[List[int]]) -> int:
    n = len(dist)
    best = float("inf")

    def backtrack(curr: int, mask: int, cost: int) -> None:
        nonlocal best
        if mask == (1 << n) - 1:
            best = min(best, cost + dist[curr][0])
            return
        if cost >= best:
            return
        for nxt in range(1, n):
            if mask & (1 << nxt):
                continue
            backtrack(nxt, mask | (1 << nxt), cost + dist[curr][nxt])

    backtrack(0, 1, 0)
    return best
Explanation:
Plain backtracking over permutations of cities 1..n-1. Prune when cost >= best. Works for small n; use bitmask DP for larger inputs.

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

Problem 2: Count number of ways/subsets using bitmasking ([Various competitive programming resources])#

Problem Statement

Given an array nums of length n, count all subsets whose elements sum to target using bitmask enumeration.

Example 1:

Input: nums = [1, 2, 3], target = 3
Output: 2
Explanation: Subsets {1, 2} and {3} sum to 3.

Example 2:

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

Constraints:

  • 1 <= n <= 20
  • 0 <= nums[i] <= 100
Code and Explanation 

1
2
3
4
5
6
7
8
def count_subsets_bitmask(nums: List[int], target: int) -> int:
    n = len(nums)
    count = 0
    for mask in range(1 << n):
        total = sum(nums[i] for i in range(n) if mask & (1 << i))
        if total == target:
            count += 1
    return count
Explanation:
Each bitmask represents a subset: bit i set means include nums[i]. Iterate all 2ⁿ masks, sum selected elements, count matches.

Time: O(n × 2ⁿ)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def count_subsets_bitmask(nums: List[int], target: int) -> int:
    n = len(nums)
    count = 0

    def backtrack(index: int, mask: int, curr_sum: int) -> None:
        nonlocal count
        if index == n:
            if curr_sum == target:
                count += 1
            return
        backtrack(index + 1, mask, curr_sum)                          # skip
        backtrack(index + 1, mask | (1 << index), curr_sum + nums[index])  # choose

    backtrack(0, 0, 0)
    return count
Explanation:
Recursive choose/skip with mask tracking which elements are included. Equivalent to bitmask iteration but builds masks via backtracking.

Time: O(2ⁿ)  |  Space: O(n)

8. Backtracking with Graph Traversal (Paths and Cycles)#

Backtracking on graphs to find all paths, cycles, or solve Hamiltonian problems.

Problem 1: Find All Paths from Source to Destination (Leetcode:797)#

Problem Statement

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1.

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]

Example 2:

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Constraints:

  • 2 <= n <= 15
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        result: List[List[int]] = []
        path = [0]

        def backtrack(node: int) -> None:
            if node == target:
                result.append(path[:])
                return
            for nxt in graph[node]:
                path.append(nxt)
                backtrack(nxt)
                path.pop()

        backtrack(0)
        return result
Explanation:
DFS from node 0, append each neighbor, recurse, pop. DAG guarantees no cycles — no visited set needed.

Time: O(2ⁿ × n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        target = len(graph) - 1
        result: List[List[int]] = []
        stack: List[List[int]] = [[0]]

        while stack:
            path = stack.pop()
            node = path[-1]
            if node == target:
                result.append(path)
                continue
            for nxt in graph[node]:
                stack.append(path + [nxt])
        return result
Explanation:
Stack holds partial paths. Pop, extend by each neighbor, push back. Same exploration order as DFS.

Time: O(2ⁿ × n)  |  Space: O(2ⁿ × n)

Problem 2: Hamiltonian Path Problem (GeeksforGeeks)#

Problem Statement

Given an undirected graph with V vertices, determine if a Hamiltonian path exists (visits every vertex exactly once).

Example 1:

Input: V = 4, edges = [[0,1],[1,2],[2,3],[0,3]]
Output: true
Explanation: Path 0→1→2→3 visits all vertices.

Example 2:

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

Constraints:

  • 1 <= V <= 10
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def hamiltonian_path(V: int, edges: List[List[int]]) -> bool:
    graph = [[] for _ in range(V)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * V

    def backtrack(vertex: int, count: int) -> bool:
        if count == V:
            return True
        for nxt in graph[vertex]:
            if not visited[nxt]:
                visited[nxt] = True
                if backtrack(nxt, count + 1):
                    return True
                visited[nxt] = False
        return False

    for start in range(V):
        visited = [False] * V
        visited[start] = True
        if backtrack(start, 1):
            return True
    return False
Explanation:
Try each start vertex. Choose neighbor → explore → unchoose visited. Success when count == V.

Time: O(V!)  |  Space: O(V)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def hamiltonian_path(V: int, edges: List[List[int]]) -> bool:
    graph = [[] for _ in range(V)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    def backtrack(vertex: int, mask: int) -> bool:
        if mask == (1 << V) - 1:
            return True
        for nxt in graph[vertex]:
            bit = 1 << nxt
            if mask & bit:
                continue
            if backtrack(nxt, mask | bit):
                return True
        return False

    for start in range(V):
        if backtrack(start, 1 << start):
            return True
    return False
Explanation:
mask tracks visited vertices as bits — compact state for small V.

Time: O(V!)  |  Space: O(V)

Problem 3: Generate Parentheses (Leetcode:22)#

Problem Statement

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

  • 1 <= n <= 8
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result: List[str] = []

        def backtrack(path: List[str], open_count: int, close_count: int) -> None:
            if len(path) == 2 * n:
                result.append("".join(path))
                return
            if open_count < n:
                path.append("(")
                backtrack(path, open_count + 1, close_count)
                path.pop()
            if close_count < open_count:
                path.append(")")
                backtrack(path, open_count, close_count + 1)
                path.pop()

        backtrack([], 0, 0)
        return result
Explanation:
Add ( if opens remain; add ) only if it won't exceed opens. Choose → explore → unchoose on path.

Time: O(4ⁿ / √n) Catalan  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        queue: List[tuple[str, int, int]] = [("", 0, 0)]
        result: List[str] = []

        while queue:
            curr, opens, closes = queue.pop(0)
            if len(curr) == 2 * n:
                result.append(curr)
                continue
            if opens < n:
                queue.append((curr + "(", opens + 1, closes))
            if closes < opens:
                queue.append((curr + ")", opens, closes + 1))
        return result
Explanation:
BFS over partial strings with open/close counts. Same validity rules, explored level by level.

Time: O(4ⁿ / √n)  |  Space: O(4ⁿ / √n)

9. Backtracking with Memoization / Top-Down DP#

Combining backtracking with caching to avoid repeated computations in overlapping subproblems.

Problem 1: Word Break II (Leetcode:140)#

Problem Statement

Given a string s and a dictionary of strings wordDict, return all sentences that can be formed by adding spaces so that each word is in the dictionary.

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Constraints:

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)
        memo: dict[int, List[str]] = {}

        def backtrack(start: int) -> List[str]:
            if start in memo:
                return memo[start]
            if start == len(s):
                return [""]
            result: List[str] = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word not in words:
                    continue
                for rest in backtrack(end):
                    result.append(word if not rest else word + " " + rest)
            memo[start] = result
            return result

        return backtrack(0)
Explanation:
At each position, try every dictionary word as the next segment. Memoize backtrack(start) to reuse partial sentence lists. Choose word → explore rest → combine.

Time: O(n² × 2ⁿ) worst case  |  Space: O(n × 2ⁿ)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)
        result: List[str] = []
        path: List[str] = []

        def backtrack(start: int) -> None:
            if start == len(s):
                result.append(" ".join(path))
                return
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word not in words:
                    continue
                path.append(word)
                backtrack(end)
                path.pop()

        backtrack(0)
        return result
Explanation:
Same segmentation tree without memo — recomputes shared suffixes. Use memo (Approach 1) when s is longer.

Time: O(n × 2ⁿ)  |  Space: O(n)

Problem 2: Letter Combinations of a Phone Number (Leetcode:17)#

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent (phone keypad mapping).

Example 1:

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

Example 2:

Input: digits = ""
Output: []

Constraints:

  • 0 <= digits.length <= 4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        mapping = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
        }
        result: List[str] = []
        path: List[str] = []

        def backtrack(index: int) -> None:
            if index == len(digits):
                result.append("".join(path))
                return
            for ch in mapping[digits[index]]:
                path.append(ch)
                backtrack(index + 1)
                path.pop()

        backtrack(0)
        return result
Explanation:
For each digit, try every mapped letter: choose → explore → unchoose. Classic combinatorial backtracking.

Time: O(4ⁿ × n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        mapping = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
        }
        result = [""]
        for d in digits:
            result = [prefix + ch for prefix in result for ch in mapping[d]]
        return result
Explanation:
Build combinations left to right by Cartesian product. Equivalent tree, explored iteratively.

Time: O(4ⁿ × n)  |  Space: O(4ⁿ)