NUHMAN.com

Backtracking is an algorithmic technique used to solve problems where you explore all possible options by recursively building a solution and abandoning (pruning) those paths that fail to meet the problem's criteria. It is particularly useful for constraint satisfaction problems, such as puzzles, combinatorics, and optimization problems.

Backtracking is essentially a depth-first search (DFS) approach where you explore all possible configurations of a problem and backtrack when you hit a dead end.

1️⃣ Backtracking: Recursive Exploration

In backtracking, we start with an empty solution and explore all potential possibilities recursively. Each time we make a decision, we check if it leads to a valid solution. If it does, we continue exploring; if not, we backtrack and try a different choice.

General Steps for Backtracking:

1. Recursively build a solution step-by-step.
2. Check constraints at each step to see if the current solution is valid.
3. If the solution is valid, recursively explore further.
4. If an invalid solution is encountered, backtrack and try a different path.

2️⃣ Pruning in Backtracking

Pruning refers to stopping the search early if a particular path is unlikely to lead to a valid solution. This helps to reduce the time complexity by avoiding the exploration of unpromising branches.

Example of Pruning:

In the N-Queens problem, once we place a queen in a row, we immediately check if the placement is valid (i.e., it doesn’t conflict with other queens). If placing a queen violates the constraints, we prune that path and backtrack.

3️⃣ Example: Solving the N-Queens Problem

One of the classic backtracking problems is the N-Queens problem, where the task is to place N queens on an NxN chessboard such that no two queens threaten each other.

Algorithm Steps:

1. Place queens one by one in columns.
2. For each queen, check if it's safe to place at the current position by ensuring no two queens share the same row, column, or diagonal.
3. If placing a queen violates the constraints, backtrack and try the next position.

Python Code (N-Queens Solution using Backtracking):

python

def solveNQueens(n):
    def is_safe(board, row, col):
        # Check the column
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def solve(board, row):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solve(board, row + 1)
                board[row] = -1  # Backtrack

    result = []
    board = [-1] * n  # -1 indicates no queen is placed in that row
    solve(board, 0)
    return result

# Test N-Queens (for 4 Queens)
n = 4
solutions = solveNQueens(n)
for solution in solutions:
    print(["." * i + "Q" + "." * (n - i - 1) for i in solution])

Explanation:

• is_safe(board, row, col) checks if placing a queen at (row, col) is safe.
• solve(board, row) recursively places queens on the board, backtracking if needed.
• The solution is stored in the result list once all queens are placed.

Time Complexity:

• The time complexity of the N-Queens problem is exponential. However, pruning helps reduce the search space significantly.

4️⃣ Common Backtracking Problems

1. Permutations (LeetCode #46)

Generate all possible permutations of a list of numbers.

• Backtracking Solution:

python

def permute(nums):
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # Swap
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]  # Backtrack

    result = []
    backtrack(0)
    return result

# Test Permutations
print(permute([1, 2, 3]))

2. Combination Sum (LeetCode #39)

Given an array of numbers, find all combinations of numbers that sum up to a target.

• Backtracking Solution:

python

def combinationSum(candidates, target):
    def backtrack(start, target, path):
        if target == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                continue
            path.append(candidates[i])
            backtrack(i, target - candidates[i], path)  # Reuse the same element
            path.pop()  # Backtrack

    result = []
    backtrack(0, target, [])
    return result

# Test Combination Sum
print(combinationSum([2, 3, 6, 7], 7))

📝 Summary

Backtracking is an essential technique for solving combinatorial problems, where you need to explore all possible solutions. By applying recursion and pruning, you can significantly optimize the process and avoid unnecessary calculations.