note0847.md

Leetcode 847. Shortest Path Visiting All Nodes

• Type: BFS
• Approach:
  1. The most tricky part to solve the problem is to find a way to represent a unique state for a node.
  2. We can use (cur_node, visited_nodes) to represent it.
  3. Use a bit int to represent the visited nodes. For instance, 0, 2, 3 were visited, so it's 1011.
  4. And our goal is to find the steps when the visited_nodes == 1111 if length of the nodes is 4.
  5. Init: push all the nodes to a queue, (node, 1 <<-- node);
• Complexity:
  • Time: O(nx2^n)
  • Space: O(nx2^n)