Coder's Cat

2020-02-10

## Challenge Description

Permutation of A[0..N] equals to:

A[1] + (A[0..N] - A[1])

A[2] + (A[0..N] - A[2])

….

A[N] + (A[0..N] - A[N])

So, the basic idea is using a recursive approach to generate all the permutations.

The time complexity: $O(N!)$.

Here we use vector<bool> used to track which elements used in Depth-Search.

## A trivial improvement with in-place approach

The above code used extra vector<bool> used to track elements usage, this could be avoided with in-place approach. This will save much used memory from stack.

And we even can iterate index which larger than current index:

So the final code is more simpler and with a better performance:

Preparing for an interview? Check out this!