Travelling Salesman Problem

Given a 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 the city 0 (0 based index) to all other cities such that you visit each city atmost once and then at the end come back to city 0 in min cost.

• Time : O(2^n * n^2)
• Space : O(n * 2^n)

c++

class Solution {
    int dp[10][1<<11];
    int helper(int mask, int target, int u, vector<vector<int>>& adj) {
        if(mask == target) {return adj[u][0];}
        if(dp[u][mask] != -1) return dp[u][mask];
        int& res = dp[u][mask] = INT_MAX;
        for(int i = 1; i < adj[u].size(); i++) {
            if(mask & (1<<i)) continue;
            res = min(res, adj[u][i] + helper(mask | (1<<i), target, i, adj));
        }
        return res;
    }
public:
    int total_cost(vector<vector<int>>cost){
        int n = cost.size();
        memset(dp, -1, sizeof dp);
        return helper(1, (1<<n) - 1, 0, cost);
    }
};