What is the time complexity of this code that generates the permutations of a set?

  algorithm, c++, time-complexity

I’ve read the following code in the competitive programmer’s handbook where search processes all of the permutations of a set that contains the elements {0,1,..., n-1}:

void search() {
    if (permutation.size() == n) {
        // process permutation
    } else {
        for (int i = 0; i < n; i++) {
            if (chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

There is a vector called permutation that contains the current elements in the permutation and an array called chosen that keeps track of which elements have already been chosen.

I understand the how the code runs, but I am struggling to understand its time complexity. I know there are n! final permutations, but it appears as though the for loop is executed more times than this. Take for example the following picture:

The for loop is executed at each node. What exactly is the time complexity of the above code?

Source: Windows Questions C++

LEAVE A COMMENT