如何使用回溯打印所有排列？

Question

此代码打印 N-1 项的所有排列。但我无法理解一件事：当 n=N 时，它返回它被调用的地方并使 flag[n-1] = false。因此，i = N-1 并中断循环。但是当 n=N-2 到 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

您需要考虑函数调用最终是嵌套的。

下面的每个缩进显示一个嵌套调用：

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)
...

因为 return 只有 returns 来自当前的函数调用，而不是所有函数调用，排列继续打印。

为了熟悉这个，试试这个：

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;
}

如何使用回溯打印所有排列？

How to print all permutation using backtracking?

c++

backtracking