Здравствуйте, lxa, Вы писали:

lxa>Алгоритм 3 без выделений дополнительной памяти и in-place показался тяжеловатым для интервью под стрессом.

А чего бы стресс? Они же там все были настроены весьма доброжелательно...

lxa>Казалось бы просто, но пришлось-таки поломать голову. Непонятно, что, может, попроще, мог упустить и где?

Как-то всё сложно... У меня получилось по-другому:

void perm(int* A, int k, int N)
{
    if (k == N) {
        for (int i = 0; i < N; i++)
            cout << A[i] << ((i == N-1) ? "\n" : " ");
    } else {
        for (int i = k; i < N; i++) {
            swap(A[k], A[i]);
            perm(A, k+1, N);
            swap(A[k], A[i]);
        }
    }
}

void main()
{
    int A[] = {5,4,3,2,1};
    perm(A, 0, 5);
}