> For the complete documentation index, see [llms.txt](https://liuzhenglaichn.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuzhenglaichn.gitbook.io/algorithm/dynamic-programming/travelling-salesperson.md).

# Travelling Salesperson

The Travelling Salesperson Problem is a classic DP problem.

The brute force solution is to enumerate all `N!` permutations of nodes.

To eliminate repetitive computations, we need to observe the fact that there is only one optimal answer (i.e. cost) for a subset of nodes, so we can memoize the optimal answer for subsets of nodes. In this way, instead of enumerating on all `N!` permutations, we just enumerate on all `2^N` subsets.

![](/files/-MatllVTzoSFP3XpYPRe)

## Problems

* [1879. Minimum XOR Sum of Two Arrays (Hard)](https://leetcode.com/problems/minimum-xor-sum-of-two-arrays/)
* [943. Find the Shortest Superstring (Hard)](https://leetcode.com/problems/find-the-shortest-superstring/)