Skip to main content

Traveling Salesman Problem

Learn Traveling Salesman Problem (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Visit Every City Exactly Once, Minimize Total Distance Brute force tries all n! orderings. Bitmask DP reduces this to O(2ⁿ × n²): the STATE is (mask, current city) , where mask is a BITMASK recording which cities have been visited. Since only "which cities visited so far" and "where I am now" matter (not the exact visiting ORDER), this compresses the state space enormously.

More lessons in Dynamic Programming