How to print all permutation using backtracking?

Question

This code prints all the permutation of N-1 items. But I could not understand one thing: when n=N, it is returning where it is called and make flag[n-1] = false. Thus, i = N-1 and breaks the loop. But how is the rest of the permutation printing or returning when n=N-2 to 0?

void perm(int n) {
    if (n == N) {
        for (int i = 0; i < N ; i++) {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (flag[i]) continue;
        a[n] = i;
        flag[i] = true;
        cout<<i<<endl;
        perm(n + 1);
        cout<<i<<endl;
        flag[i] = false;

    }
}

Answer 1

You need to consider that function calls ended up nested.

Each indentation below shows a nested call:

main()
    entering perm(0)
        entering perm(1)
            i = 0
            entering perm(2)
                let's say N is 2, this will print and return

        now perm(1) continues
            i becomes 1
            entering perm(2)
...
        

Since return only returns from the current function call, not all function calls, the permutations continue printing.

In order to gain familiarity with this, try this:

void perm(int n) {
std::cout << "Entering perm " << n << std::endl;
if (n == N) {
    for (int i = 0; i < N ; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    std::cout << "Exiting perm " << n << std::endl;
    return;
}
for (int i = 0; i < N; i++) {
    if (flag[i]) continue;
    a[n] = i;
    flag[i] = true;
    cout<<i<<endl;
    std::cout << "about to call perm" << std::endl;
    perm(n + 1);
    std::cout << "finished call to perm" << std::endl;
    cout<<i<<endl;
    flag[i] = false;

}
    std::cout << "Exiting perm " << n << " (2)"<< std::endl;
}