Bitmask DP vs Backtracking for TSP: When $O(N^2 \cdot 2^N)$ Beats $O(N!)$

The Moment Backtracking Falls Apart

Backtracking solves TSP for 10 cities in 0.09 seconds. Bump that to 15 cities, and you're waiting 4+ seconds. Bitmask DP handles 15 cities in under 0.02 seconds — roughly 200x faster.

The algorithmic gap between these two approaches becomes a cliff once $N$ exceeds 12. I ran both implementations head-to-head on identical distance matrices, and the numbers don't lie. If you're prepping for coding interviews and think "I'll just use backtracking with pruning," this post might change your mind.

Why TSP Makes Interviewers Smile

The Traveling Salesman Problem shows up constantly in interviews disguised as other problems: minimum cost to visit all nodes, shortest hamiltonian path, optimal delivery route. The core is always the same — visit every vertex exactly once and minimize total cost.

The brute force complexity is $O(N!)$ which explodes hilariously fast. For $N=10$, that's 3.6 million permutations. For $N=15$, it's over 1.3 trillion. No amount of clever pruning saves you from factorial growth.

Bitmask DP drops this to $O(N^2 \cdot 2^N)$. For $N=15$, that's roughly 7.4 million operations. Still exponential, but polynomial in the exponent makes all the difference.

The Backtracking Baseline

Let's start with what most people reach for first. Here's a clean backtracking implementation with basic pruning:

python
import time
import random

def tsp_backtracking(dist):
    n = len(dist)
    if n == 0:
        return 0

---

*Continue reading the full article on [TildAlice](https://tildalice.io/bitmask-dp-vs-backtracking-tsp-benchmark/)*