TSP Held-Karp State Count

Problem

Run the Held-Karp bitmask DP and report how many states are reachable plus the optimal tour cost.

dist is a symmetric matrix where dist[i][j] = -1 marks a missing edge; dp[mask][j] is the cheapest path starting at 0, visiting exactly the nodes in mask, and ending at j. Count every finite state, including the initial state (mask = 1, j = 0). Return [state_count, optimal_cost], with optimal_cost = -1 when no Hamiltonian cycle exists.

Hint

Adding a node extends the mask and gives one new state per possible last city.

Test cases

case 1

in: [4,[[0,1,2,3],[1,0,4,5],[2,4,0,6],[3,5,6,0]]]

expected: [13,14]

case 2

in: [4,[[0,1,-1,3],[1,0,4,-1],[-1,4,0,6],[3,-1,6,0]]]

expected: [7,14]

case 3

in: [3,[[0,2,3],[2,0,4],[3,4,0]]]

expected: [5,9]

case 4

in: [1,[[0]]]

expected: [1,0]

case 5

in: [3,[[0,1,-1],[1,0,-1],[-1,-1,0]]]

expected: [2,-1]

Starter codePython

def tsp_bitmask_state_count(n, dist):
    # Your code here
    pass

5 test cases · run your code against them in the editor