Backtracking (Hard)Solve constraint satisfaction problems and finding all solutions using recursion.

46. Permutations

Problem Statement

Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in any order. **Example:** ```python 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. **Backtracking**: We need to explore all orderings. 2. **State**: Current permutation built so far. 3. **Choice**: For the next position, choose any number that hasn't been used yet. 4. **Base Case**: If the current permutation length equals `len(nums)`, add to results.

Solution

def permute(nums):
    res = []
    
    def backtrack(curr):
        if len(curr) == len(nums):
            res.append(curr[:])
            return
            
        for n in nums:
            if n not in curr:
                curr.append(n)
                backtrack(curr)
                curr.pop()
                
    backtrack([])
    return res

78. Subsets

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:** ```python Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] ```

Approach

1. **Choice**: For each element, we have two choices: include it or exclude it. 2. **DFS Tree**: * Index `i`: Include `nums[i]` -> recurse `i+1`. * Index `i`: Exclude `nums[i]` -> recurse `i+1`. 3. **Base Case**: When `i == len(nums)`, add current subset to result.

Solution

def subsets(nums):
    res = []
    subset = []
    
    def dfs(i):
        if i >= len(nums):
            res.append(subset[:])
            return
            
        # Decision to include nums[i]
        subset.append(nums[i])
        dfs(i + 1)
        
        # Decision NOT to include nums[i]
        subset.pop()
        dfs(i + 1)
        
    dfs(0)
    return res

39. Combination Sum

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. **Example:** ```python Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] ```

Approach

1. **Decision Tree**: At each index `i`, we can either pick `candidates[i]` (stay at `i`) if valid, or move to `i+1`. 2. **Constraints**: * Total sum > target -> invalid. * Total sum == target -> valid solution. * Index out of bounds -> stop.

Solution

def combinationSum(candidates, target):
    res = []
    
    def dfs(i, cur, total):
        if total == target:
            res.append(cur.copy())
            return
        if i >= len(candidates) or total > target:
            return
            
        # Include candidates[i]
        cur.append(candidates[i])
        dfs(i, cur, total + candidates[i])
        
        # Exclude candidates[i]
        cur.pop()
        dfs(i + 1, cur, total)
        
    dfs(0, [], 0)
    return res

79. Word Search

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:** ```python Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true ```

Approach

1. **DFS on Grid**: Start DFS from every cell `(r, c)`. 2. **Validation**: * Check boundaries. * Check if `board[r][c]` matches current character in word. * Check if `visited`. 3. **Recursion**: If match, mark visited, search neighbors for next char, then backtrack (unmark visited).

Solution

def exist(board, word):
    ROWS, COLS = len(board), len(board[0])
    path = set()
    
    def dfs(r, c, i):
        if i == len(word):
            return True
        if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
            word[i] != board[r][c] or (r, c) in path):
            return False
            
        path.add((r, c))
        res = (dfs(r + 1, c, i + 1) or
               dfs(r - 1, c, i + 1) or
               dfs(r, c + 1, i + 1) or
               dfs(r, c - 1, i + 1))
        path.remove((r, c))
        return res
        
    for r in range(ROWS):
        for c in range(COLS):
            if dfs(r, c, 0):
                return True
                
    return False

51. N-Queens

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. **Example:** ```python Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] ```

Approach

1. **Constraint**: Queens attack row, col, and diagonals. 2. **Tracking**: * Columns used (`cols`). * Positive diagonals (`r + c`). * Negative diagonals (`r - c`). 3. **Backtracking**: Iterate through rows. For each col in row, check constraints. If valid, place queen and recurse to next row.

Solution

def solveNQueens(n):
    col = set()
    posDiag = set() # (r + c)
    negDiag = set() # (r - c)
    
    res = []
    board = [["."] * n for i in range(n)]
    
    def backtrack(r):
        if r == n:
            copy = ["".join(row) for row in board]
            res.append(copy)
            return
            
        for c in range(n):
            if c in col or (r + c) in posDiag or (r - c) in negDiag:
                continue
                
            col.add(c)
            posDiag.add(r + c)
            negDiag.add(r - c)
            board[r][c] = "Q"
            
            backtrack(r + 1)
            
            col.remove(c)
            posDiag.remove(r + c)
            negDiag.remove(r - c)
            board[r][c] = "."
            
    backtrack(0)
    return res

Back

Backtracking (Hard) / 46. Permutations

00:00

1/5

46. Permutations

Medium

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

Example:

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

1
Backtracking: We need to explore all orderings.
2
State: Current permutation built so far.
3
Choice: For the next position, choose any number that hasn't been used yet.
4
Base Case: If the current permutation length equals len(nums), add to results.

PYTHON PLAYGROUND

⏳ Loading editor…