Hey everyone. I was looking at the code in CP3 book to solve the TSP using top-down DP in O(n^2*2^n) and was trying to print the path, but it seems impossible to me.

I thought about creating something like a "parent" array and then reconstruct, but couldn't.

This is the code:

static void tsp() {
// n = graph's number of vertices
memo = new double[n][1 << n];
for (int i = 0; i < n; ++i)
	for (int j = 0; j < 1 << n; ++j)
		memo[i][j] = Double.MIN_VALUE;
double distance = tsp(0, 1);
// Build ath - pending
System.out.println("Distance:" + distance);
}

static double dp(int pos, int bitmask) {
	if (bitmask == (1 << n) - 1)
		return graph[pos][0];
	if (Double.compare(memo[pos][bitmask], Double.MIN_VALUE) != 0)
		return memo[pos][bitmask];
	double ans = Double.MAX_VALUE;
	for (int nxt = 0; nxt < n; ++nxt)
		if (nxt != pos && (bitmask & (1 << nxt)) == 0)
			ans = Double.min(ans, graph[pos][nxt] + dp(nxt, bitmask | (1 << nxt)));
	memo[pos][bitmask] = ans;
	return ans;
}

Any help? Thanks!