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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { int dp[10][1<<11]; inthelper(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: inttotal_cost(vector<vector<int>>cost){ int n = cost.size(); memset(dp, -1, sizeof dp); returnhelper(1, (1<<n) - 1, 0, cost); } };