Time complexity of the travelling salesman problem (Recursive formulation)
The full recursion tree for your problem has as root $(1,\{2,\ldots,n\})$. The children of a node $(i,S)$ are $(j,S \setminus \{j\})$, where $j$ ranges over all elements of $j$. Nodes with $S = \emptyset$ have no children.
Let us annotate each node in the tree by its &quot;history&quot;. Instead of annotating each node by an index and a set, we annotate it with a sequence and a set. The root is $(1;\{2,\ldots,n\})$. The children of a node $(a;S)$ are $(a,j;S \setminus \{j\})$ for all $j \in S$. For example, if $n = 3$ then the nodes are:

$(1;\{2,3\})$.
$(1,2;\{3\})$.
$(1,3;\{2\})$.
$(1,2,3;\emptyset)$.
$(1,3,2;\emptyset)$.

A node $(a_1,\ldots,a_m;S)$ in the new tree corresponds to the node $(a_m,S)$ in the original tree. Conversely, each node $(a,S)$ corresponds to nodes $(1,a_2,\ldots,a_{m-1},a;S)$, where $m = n - |S|$ and $\{1,a_2,\ldots,a_{m-1},a\} = \overline{S}$. There are $(n-2-|S|)!$ ways to choose $a_2,\ldots,a_{m-1}$, and so the node $(a,S)$ appears $(n-2-|S|)!$ times in the original tree.
This shows that the full recursion tree for your problem does contain duplicates.