03. Travelling Salesman Problem

✅ GFG solution to the Travelling Salesman Problem: find minimum cost to visit all cities exactly once and return to start using dynamic programming with bitmask optimization. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given a 2D matrix cost[][] of size n where cost[i][j] denotes the cost of moving from city i to city j. Your task is to complete a tour from city 0 (0-based index) to all other cities such that you visit each city exactly once and then at the end come back to city 0 at minimum cost.

This is the classic Travelling Salesman Problem (TSP), where the goal is to find the shortest possible route that visits every city exactly once and returns to the starting city.

📘 Examples

Example 1

Input: cost[][] = [[0, 111], 
                   [112, 0]]
Output: 223
Explanation: We can visit 0->1->0 and cost = 111 + 112 = 223.

Example 2

Input: cost[][] = [[0, 1000, 5000],
                   [5000, 0, 1000],
                   [1000, 5000, 0]]
Output: 3000
Explanation: We can visit 0->1->2->0 and cost = 1000 + 1000 + 1000 = 3000.

🔒 Constraints

$1 \le \text{cost.size()} \le 15$
$0 \le \text{cost}[i][j] \le 10^4$

✅ My Approach

The optimal approach uses Dynamic Programming with Bitmask (Held-Karp algorithm) to efficiently explore all possible tours:

Bitmask Dynamic Programming

State Representation:
- Use dp[mask][i] to represent the minimum cost to visit all cities represented by set bits in mask, ending at city i.
- The bitmask mask tracks which cities have been visited (bit i is 1 if city i is visited).
Base Case:
- Start from city 0: dp[1][0] = 0 (only city 0 visited with cost 0).
State Transitions:
- For each state (mask, i), try moving to every unvisited city j.
- Update dp[mask | (1 << j)][j] with the minimum of current value and dp[mask][i] + cost[i][j].
Final Answer:
- After visiting all cities (when mask = 2^n - 1), add the cost to return to city 0.
- The answer is min(dp[fullMask][i] + cost[i][0]) for all cities i.
Optimization:
- Process states in order of increasing mask values to ensure all dependencies are resolved.
- Skip invalid states where city i is not in the mask or cost is infinity.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n² × 2ⁿ), where n is the number of cities. We have 2ⁿ possible subsets of cities and for each subset-city combination, we try to extend to n other cities.
Expected Auxiliary Space Complexity: O(n × 2ⁿ), as we maintain a 2D DP table with dimensions (2ⁿ × n) to store the minimum cost for each state.

🧑‍💻 Code (C++)

class Solution {
public:
    int tsp(vector<vector<int>>& cost) {
        int n = cost.size();
        if (n <= 1) return n ? cost[0][0] : 0;
        int FULL = (1 << n) - 1;
        vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
        dp[1][0] = 0;
        for (int mask = 1; mask <= FULL; mask++) {
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i)) || dp[mask][i] == INT_MAX) continue;
                for (int j = 0; j < n; j++) {
                    if (mask & (1 << j)) continue;
                    int nxt = mask | (1 << j);
                    dp[nxt][j] = min(dp[nxt][j], dp[mask][i] + cost[i][j]);
                }
            }
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; i++)
            if (dp[FULL][i] != INT_MAX)
                ans = min(ans, dp[FULL][i] + cost[i][0]);
        return ans;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Recursive Memoization Approach

💡 Algorithm Steps:

Use recursion with memoization to explore all paths starting from city 0.
Track visited cities using bitmask and current city position.
Store computed results in memo table to avoid recomputation.
Return to starting city after visiting all cities to complete the tour.

class Solution {
public:
    int tsp(vector<vector<int>>& cost) {
        int n = cost.size();
        if (n <= 1) return n ? cost[0][0] : 0;
        vector<vector<int>> memo(1 << n, vector<int>(n, -1));
        function<int(int, int)> solve = [&](int mask, int pos) {
            if (mask == (1 << n) - 1) return cost[pos][0];
            if (memo[mask][pos] != -1) return memo[mask][pos];
            int res = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i))) {
                    res = min(res, cost[pos][i] + solve(mask | (1 << i), i));
                }
            }
            return memo[mask][pos] = res;
        };
        return solve(1, 0);
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n² × 2ⁿ) - Exploring all subsets with transitions
Auxiliary Space: 💾 O(n × 2ⁿ) - Memoization table and recursion stack

✅ Why This Approach?

Top-down approach easier to understand and debug
Natural recursive structure matches problem definition
Clean code with lambda functions for modern C++

📊 3️⃣ Space-Optimized Bottom-Up DP

💡 Algorithm Steps:

Process states layer by layer based on number of visited cities.
Use two arrays to track current and next layer states.
Reduce space by only keeping necessary previous states.
Calculate minimum cost by building solutions incrementally.

class Solution {
public:
    int tsp(vector<vector<int>>& cost) {
        int n = cost.size();
        if (n <= 1) return n ? cost[0][0] : 0;
        map<pair<int,int>, int> curr, next;
        curr[{1, 0}] = 0;
        for (int cnt = 1; cnt < n; cnt++) {
            next.clear();
            for (auto& [key, val] : curr) {
                int mask = key.first, pos = key.second;
                for (int i = 0; i < n; i++) {
                    if (mask & (1 << i)) continue;
                    int nmask = mask | (1 << i);
                    if (!next.count({nmask, i}) || next[{nmask, i}] > val + cost[pos][i])
                        next[{nmask, i}] = val + cost[pos][i];
                }
            }
            curr = next;
        }
        int ans = INT_MAX;
        for (auto& [key, val] : curr)
            ans = min(ans, val + cost[key.second][0]);
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n² × 2ⁿ) - Same state transitions
Auxiliary Space: 💾 O(n × 2ⁿ⁻¹) - Only store reachable states

✅ Why This Approach?

Memory efficient by storing only necessary states
Avoids allocating full 2D array for sparse graphs
Better cache locality for smaller problem instances

Note: This approach results in Time Limit Exceeded (TLE) for large inputs (fails ~1110/1115 test cases due to time constraints).

📊 4️⃣ Held-Karp with Path Reconstruction

💡 Algorithm Steps:

Build DP table similar to standard approach but track parent information.
Store both minimum cost and previous city for each state.
After finding optimal cost reconstruct the actual path taken.
Useful when both cost and path sequence are needed.

class Solution {
public:
    int tsp(vector<vector<int>>& cost) {
        int n = cost.size();
        if (n <= 1) return n ? cost[0][0] : 0;
        vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
        vector<vector<int>> parent(1 << n, vector<int>(n, -1));
        dp[1][0] = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i)) || dp[mask][i] == INT_MAX) continue;
                for (int j = 0; j < n; j++) {
                    if (mask & (1 << j)) continue;
                    int nxt = mask | (1 << j);
                    if (dp[nxt][j] > dp[mask][i] + cost[i][j]) {
                        dp[nxt][j] = dp[mask][i] + cost[i][j];
                        parent[nxt][j] = i;
                    }
                }
            }
        }
        int ans = INT_MAX, lastCity = -1;
        for (int i = 0; i < n; i++) {
            if (dp[(1 << n) - 1][i] != INT_MAX && ans > dp[(1 << n) - 1][i] + cost[i][0]) {
                ans = dp[(1 << n) - 1][i] + cost[i][0];
                lastCity = i;
            }
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n² × 2ⁿ) - Standard DP with parent tracking
Auxiliary Space: 💾 O(n × 2ⁿ) - Additional parent array

✅ Why This Approach?

Provides both optimal cost and actual tour path
Essential for applications needing the route details
Minimal overhead compared to basic DP solution

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🏷️ Bottom-Up DP

🟢 O(n² × 2ⁿ)

🟡 O(n × 2ⁿ)

🚀 Iterative, no stack overflow

💾 Full state space allocation

🔍 Recursive Memoization

🟢 O(n² × 2ⁿ)

🟡 O(n × 2ⁿ)

📖 Intuitive top-down logic

🔧 Recursion stack overhead

📊 Space-Optimized

🟢 O(n² × 2ⁿ)

🟢 O(n × 2ⁿ⁻¹)

💾 Reduced memory footprint

🔧 More complex state management

🔄 Path Reconstruction

🟢 O(n² × 2ⁿ)

🟡 O(n × 2ⁿ)

⭐ Returns both cost and path

💾 Extra space for parent tracking

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

🏅 Standard TSP problem

🥇 Bottom-Up DP

★★★★★

📖 Learning/Understanding

🥈 Recursive Memoization

★★★★☆

💾 Memory-constrained

🥉 Space-Optimized

★★★★☆

🎯 Need actual tour path

🏅 Path Reconstruction

★★★★★

☕ Code (Java)

class Solution {
    public int tsp(int[][] cost) {
        int n = cost.length;
        if (n <= 1) return n == 1 ? cost[0][0] : 0;
        int FULL = (1 << n) - 1;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[1][0] = 0;
        for (int mask = 1; mask <= FULL; mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 || dp[mask][i] == Integer.MAX_VALUE) continue;
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) != 0) continue;
                    int nxt = mask | (1 << j);
                    dp[nxt][j] = Math.min(dp[nxt][j], dp[mask][i] + cost[i][j]);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++)
            if (dp[FULL][i] != Integer.MAX_VALUE)
                ans = Math.min(ans, dp[FULL][i] + cost[i][0]);
        return ans;
    }
}

🐍 Code (Python)

class Solution:
    def tsp(self, cost):
        n = len(cost)
        if n <= 1: return cost[0][0] if n else 0
        FULL = (1 << n) - 1
        dp = [[float('inf')] * n for _ in range(1 << n)]
        dp[1][0] = 0
        for mask in range(1, (1 << n)):
            for i in range(n):
                if not (mask & (1 << i)) or dp[mask][i] == float('inf'): continue
                for j in range(n):
                    if mask & (1 << j): continue
                    nxt = mask | (1 << j)
                    dp[nxt][j] = min(dp[nxt][j], dp[mask][i] + cost[i][j])
        ans = float('inf')
        for i in range(n):
            if dp[FULL][i] != float('inf'):
                ans = min(ans, dp[FULL][i] + cost[i][0])
        return ans

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous02. Maximise String Score Next04. Optimal Binary Search Tree

Last updated 1 month ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagBitmask Dynamic Programming

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Recursive Memoization Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Space-Optimized Bottom-Up DP

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Held-Karp with Path Reconstruction

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

🔒 Constraints

✅ My Approach

Bitmask Dynamic Programming

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Recursive Memoization Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Space-Optimized Bottom-Up DP

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Held-Karp with Path Reconstruction

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count