Time complexity of the travelling salesman problem (Recursive formulation) According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (neighbor vector is the same set and v is cost matrix):
recursion formula :
C(i,S) = min { d(i,j) + C(j,S-{j}) }

my code :
#include &lt;iostream&gt;
#include &lt;vector&gt;
#define INF 99999
using namespace std;
vector&lt;vector&lt;int&gt;&gt; v{ { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };
vector&lt;int&gt; erase(vector&lt;int&gt; v, int j)
{
    v.erase(v.begin() + j);
    vector&lt;int&gt; vv = v;
    return vv;
}
int TSP(vector&lt;int&gt; neighbor, int index)
{
    if (neighbor.size() == 0)
        return v[index][0];
    int min = INF;
    for (int j = 0; j &lt; neighbor.size(); j++)
    {
        int cost = v[index][neighbor[j]] + TSP(erase(neighbor, j), neighbor[j]);
        if (cost &lt; min)
            min = cost;
    }
    return min;
}
int main()
{
    vector&lt;int&gt; neighbor{ 1, 2, 3 };
    cout &lt;&lt; TSP(neighbor, 0) &lt;&lt; endl;
    return 0;
}

In fact, the erase function removes the element j from the set (which is the neighbor vector)
I know about dynamic programming that prevents duplicate calculations (like the Fibonacci function) but it does not have duplicate calculations because if we draw the tree of this function we see that the arguments of function (i.e. S and i in formula and like the picture below) are never the same and there is no duplicate calculation.
My question is, is this time O(n!)?
picture :
If yes,why? This function is exactly the same as the formula and it does exactly the same thing. Where is the problem? Is it doing duplicate calculations?
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.