Counting and Bitmask DP

Opening scenario

Problem references use LC for LeetCode.

You have n dice each with k faces (1..k). Return the number of ways to roll them so the face values sum to target, modulo 1e9+7 (LC 1155, Number of Dice Rolls With Target Sum). Then the interviewer twists it. You are given an undirected connected graph of n nodes. Return the length of the shortest walk that visits every node. You may revisit nodes and edges, and you may start anywhere (LC 847, Shortest Path Visiting All Nodes).

The dice are distinguishable: rolling (1, 2) and (2, 1) counts as two outcomes. The graph example uses unweighted edges, measures walk length in edges, and has 1 ≤ n ≤ 12. Begin by identifying when two different partial choices leave exactly the same work to finish.

Question progression

Q1 — When the objective is "how many ways", what is the state and the transition?

Question: For LC 1155 you could recurse "for each die, try faces 1..k". What is…