递归看不明白了求大家帮助

Question

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
void pai(stack<int>&s,vector<bool> &used,int n){
    //dfs第一步 结束处理
    int i;
    if(s.size()==n){//此时已经生成出一个排序的结果
        stack<int>temp;//创建一个临时栈保存原栈中的元素，避免先进后出出完
        string result;
        while(!s.empty()){
            temp.push(s.top());
            result=('0'+(char)s.top())+result;
            s.pop();
        }
        cout<<result<<endl;
        while(!s.empty()){
            s.push(temp.top());
            temp.pop();
        }//最后将保留到预留栈中的元素返回到老栈中，恢复现场
        return;
    }

    //第二部暴力枚举 数据处理 
    for(i=1;i<=n;i++){
        if(!used[i]){//如果该位置没有被用过
            used[i]=true;
            s.push(i);
            pai(s,used,n);
            //递归后回溯语句
            s.pop();
            used[i]=false;
        }
    }
    //1 2 3
    //从i=1开始
    //used[i]即为当前(i)有没有使用过 
    //没有用的话压入栈s中 
}
int main(){
    int n;
    cin>>n;
    stack<int>s;
    vector<bool>used(n+1,flase);//定义一个顺序表来记录数字是是否被用过，并且赋初始值为0
    pai(s,used,n);
    return 0;
}

这里不明白递归是怎么回溯的，到底是怎么执行的，是怎么得出来132这种结果的呀，第一次学dfs一直没想明白，可不可以那输入3举个例子讲一下是怎么一步一步输出出来全排列的各种结果的呀 ，谢谢大家

Answer 1

初始化 n = 3，used 数组为 {false, false, false, false}。
调用 pai 函数，栈 s 为空。

pai(s, used, 3)
    |
    v
s.isEmpty() == false (因为 s.size() != 3)
   |
   v
for (int i = 1; i <= 3; i++) {
    |
    v
i = 1, used[1] == false
    |
    v
used[1] = true
    s.push(1)
    pai(s, used, 3)
        |
        v
    s == {1}
    s.size() == 3
    |
    ^ (返回上一层递归)
    |
    v
i = 2, used[1] == true, 跳过
    |
    v
i = 3, used[3] == false
    |
    v
used[3] = true
    s.push(3)
    pai(s, used, 3)
        |
        v
    s == {1, 3}
    s.size() == 3
    |
    ^ (返回上一层递归)
    |
    v
s.pop() == 3
    used[3] = false
    |
    v
s == {1}
    |
    v
i = 2, used[2] == false
    |
    v
used[2] = true
    s.push(2)
    pai(s, used, 3)
        |
        v
    s == {1, 2}
    s.size() == 3
    |
    ^ (返回上一层递归)
        |
        v
    s.pop() == 2
    used[2] = false
    |
    v
s == {1}
    |
    v
s.pop() == 1
    used[1] = false

以上，得到了第一个全排列 1。继续这个过程：
for (int i = 1; i <= 3; i++) {
    |
    v
i = 1, used[1] == true, 跳过
    |
    v
i = 2, used[2] == false
    |
    v
used[2] = true
    s.push(2)
    pai(s, used, 3)
        |
        v
    s == {2}
    s.size() == 3
    |
    ^ (返回上一层递归)
        |
        v
    i = 3, used[3] == false
        |
        v
    used[3] = true
    s.push(3)
    pai(s, used, 3)
        |
        v
    s == {2, 3}
    s.size() == 3
    |
    ^ (返回上一层递归)
        |
        v
    s.pop() == 3
    used[3] = false
        |
        v
    s == {2}
        |
        v
    s.push(1)
    pai(s, used, 3)
        |
        v
    s == {2, 1}
    s.size() == 3
    |
    ^ (返回上一层递归)
        |
        v
    s.pop() == 1
    used[1] = false
        |
        v
    s == {2}
        |
        v
    s.pop() == 2
    used[2] = false

得到了第二个全排列 23。继续这个过程，直到找到所有的全排列：
...............