u/Aphrontic_Alchemist

I tried adapting the C++ implementation in Rosetta Code:

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;

void heldKarpMax(const vector<vector<ull>>& dist) {
  int numberOfCities = dist.size(),
      totalSubsets = 1 << numberOfCities;

  // dp[mask][j] = max cost to start at 0, visit exactly the cities in mask, and end at j
  vector<vector<ull>> dp(totalSubsets, vector<ull>(numberOfCities, 0));
  // parent[mask][j] = best predecessor of j in the optimal path for (mask, j)
  vector<vector<int>> parent(totalSubsets, vector<int>(numberOfCities, -1));
  // base case: mask = (1<<0), at city 0, cost = 0
  dp[1][0] = 0;  
  
  // Build up DP table
  for(int mask = 1; mask < totalSubsets; ++mask) {
    // Always include city 0 in the tour
    if(!(mask & 1)) continue;
    for(int j = 1; j < numberOfCities; ++j) {
      //  Skip if city j isn't in the current subset
      if(!(mask & (1 << j))) continue;
      int prevMask = mask ^ (1 << j);
      for(int k = 0; k < numberOfCities; ++k) {
      // Skip if city k isn't in the previous subset
        if(!(prevMask & (1 << k))) continue;
        ull cost = dp[prevMask][k] + dist[k][j];
        if(cost > dp[mask][j]) {
          dp[mask][j] = cost;
          parent[mask][j] = k;
        }
      }
    }
  }

  // Close the tour by returning to city 0
  int fullMask = totalSubsets - 1,
      lastCity = -1;
  ull maxCost = 0;
  for(int j = 1; j < numberOfCities; ++j) {
  ull cost = dp[fullMask][j] + dist[j][0];
    if(cost > maxCost) {
      maxCost = cost;
      lastCity = j;
    }
  }
    
  // Reconstruct the optimal tour
  vector<int> tour;
  int mask = fullMask, 
      cur = lastCity;
  while(cur != -1) {
    tour.push_back(cur);
    int p = parent[mask][cur];
    mask ^= (1 << cur);
    cur = p;
  }

  // Put city 0 at both ends of the tour
  reverse(tour.begin(), tour.end());
  tour.push_back(0);

  // Print the cost and tour
  cout << "Longest  tour: ";
  for(int i = 0; i < tour.size(); i++) 
    cout << tour[i] << (i != tour.size() - 1 ? " -> " : " ");
  cout << "at " << maxCost << " units\n";
}

int main(void) {
  vector<vector<ull>> dist = {
    { 0,  2, 15, 10},
    { 2,  0,  7,  4},
    {15,  7,  0, 12},
    {10,  4, 12,  0}
  };

  heldKarpMax(dist);
}

The result in the terminal is

Longest  tour: 0 -> 3 -> 2 -> 0 at 37 units

when it should be

Longest  tour: 0 -> 3 -> 1 -> 2 -> 0 at 36 units

Strangely, these adjacency matrices:

vector<vector<ull>> dist = {
  { 0,  2, 15, 10, 19},
  { 2,  0,  7,  4,  8},
  {15,  7,  0, 12,  3},
  {10,  4, 12,  0,  6},
  {19,  8,  3,  6,  0}
};

and

vector<vector<ull>> dist = {
  { 0,  1,  2,  3},
  { 1,  0,  1,  2},
  { 2,  1,  0,  1},
  { 3,  2,  1,  0}
 };

give the correct result:

Longest  tour: 0 -> 4 -> 1 -> 3 -> 2 -> 0 at 58 units

and

Longest  tour: 0 -> 3 -> 1 -> 2 -> 0 at 8 units

respectively, so the algorithm only works for some adjacency matrices. I know the results are correct, since I hand-checked them.