How to calculate time complexity of backtracking algorithm?

Demystifying Backtracking: A Guide to Time Complexity Analysis

Understand how to calculate the time complexity of backtracking algorithms, a crucial skill for optimizing recursive solutions to combinatorial problems.

Backtracking is a general algorithmic technique for finding all (or some) solutions to computational problems that incrementally build candidates to the solutions. It abandons a candidate ('backtracks') as soon as it determines that the candidate cannot possibly be completed to a valid solution. While powerful, backtracking algorithms can be computationally expensive. Analyzing their time complexity is essential for predicting performance and identifying bottlenecks.

The Nature of Backtracking and Its Complexity

Backtracking algorithms often explore a state-space tree. Each node in the tree represents a partial solution, and edges represent choices made to extend that solution. The algorithm traverses this tree, pruning branches that cannot lead to a valid solution. The time complexity is typically determined by the number of nodes visited in this implicit search tree and the work done at each node.

flowchart TD
    A[Start Backtracking] --> B{Make a Choice}
    B --> C{Is Choice Valid?}
    C -->|No| D[Backtrack: Undo Choice]
    C -->|Yes| E{Is Solution Complete?}
    E -->|Yes| F[Record Solution]
    E -->|No| B
    F --> D

A simplified flowchart of the backtracking process.

Key Factors Influencing Time Complexity

Several factors contribute to the time complexity of a backtracking algorithm:

1. Branching Factor (b): The maximum number of choices available at each decision point.
2. Depth of the Recursion (d): The maximum length of a valid solution or the maximum depth of the state-space tree.
3. Work per Node (W): The amount of computation performed at each node (e.g., checking constraints, copying data, making a choice).
4. Pruning Efficiency: How effectively the algorithm prunes invalid branches. Good pruning can significantly reduce the number of nodes visited.

In the worst case, a backtracking algorithm might explore every possible path in the state-space tree up to a certain depth. If there are b choices at each of d levels, the total number of nodes in a full tree would be approximately b^d. Therefore, the worst-case time complexity often looks like O(b^d * W).

Analyzing Specific Examples

Let's consider common backtracking problems to illustrate complexity analysis.

Example 1: N-Queens Problem

The N-Queens problem asks us to place N chess queens on an N×N chessboard such that no two queens attack each other. Each queen must be in its own row, column, and diagonal.

• Branching Factor: In the worst case, for each row, we try to place a queen in one of the N columns. So, b = N.
• Depth: We need to place N queens, one in each row. So, d = N.
• Work per Node: At each step, we check if placing a queen in a particular column is safe. This involves checking the current column and two diagonals, which takes O(N) time (or O(1) if using hash sets/bitmasks for constant time lookups, but O(N) for simple iteration).

Therefore, the worst-case time complexity is approximately O(N^N * N) = O(N^(N+1)). However, due to effective pruning (a queen cannot be placed in an attacked position), the actual number of states explored is much less, closer to O(N!) or O(N^N) in practice, but still exponential.

def solveNQueens(n: int) -> list[list[str]]:
    board = [['.' for _ in range(n)] for _ in range(n)]
    solutions = []

    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        # Check upper left diagonal
        r, c = row - 1, col - 1
        while r >= 0 and c >= 0:
            if board[r][c] == 'Q':
                return False
            r -= 1
            c -= 1
        # Check upper right diagonal
        r, c = row - 1, col + 1
        while r >= 0 and c < n:
            if board[r][c] == 'Q':
                return False
            r -= 1
            c += 1
        return True

    def backtrack(row):
        if row == n:
            solutions.append([''.join(r) for r in board])
            return

        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.' # Backtrack

    backtrack(0)
    return solutions

Python implementation of the N-Queens problem using backtracking.

Example 2: Subset Sum Problem

Given a set of non-negative integers and a target sum, determine if there is a subset of the given set whose sum equals the target sum.

• Branching Factor: For each element, we have two choices: either include it in the subset or exclude it. So, b = 2.
• Depth: The depth of the recursion is equal to the number of elements in the set, N. So, d = N.
• Work per Node: At each node, we perform constant time operations (addition, comparison). So, W = O(1).

Therefore, the worst-case time complexity is O(2^N * 1) = O(2^N). This is because, in the worst case, we might explore all 2^N possible subsets.

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (totalSum % 2 != 0) {
            return false; // Cannot partition into two equal subsets
        }
        int target = totalSum / 2;
        return canFindSubsetSum(nums, target, 0);
    }

    private boolean canFindSubsetSum(int[] nums, int target, int index) {
        if (target == 0) {
            return true;
        }
        if (target < 0 || index == nums.length) {
            return false;
        }

        // Option 1: Include current element
        if (canFindSubsetSum(nums, target - nums[index], index + 1)) {
            return true;
        }

        // Option 2: Exclude current element
        return canFindSubsetSum(nums, target, index + 1);
    }
}

Java implementation for a variation of Subset Sum (Equal Subset Sum Partition) using backtracking.