题解|老子的全排列呢

首先，这道题要求很简单，就是要求输出1~8的全排列。

这里我们需要做到：一：一个排列里，一个数字只出现一次。这里我们可以用一个布尔数组进行跟踪，通过布尔数组来判断该数字是否出现过。二：排列不能重复。这里我们可以用循环进行单向遍历，保证情况不重复。为了实现上面要求，我们需要有一个状态的记录过程，那我们很容易联想到递归。

看整体代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

void pailie(vector<int> &vec,int* nums,int num);
void pri_pailie(vector<int> &vec);
int main(){
    int nums[9]={};
    vector<int> vec;
    pailie(vec,nums,8);
    return 0;
}

//核心函数就在这里
void pailie(vector<int> &vec,int* nums,int num){
    if(vec.size()>=num){	//如果向量长度已经达标，则打印输出。
        pri_pailie(vec);
        return;
    }
    if(vec.empty()) for(int i=1;i<=num;i++) nums[i]=0;
    
    for(int i=1;i<=num;i++){//遍历1~8
        if(!nums[i]){	//如果i未被访问，则push进向量传给下一个。
            vec.push_back(i);
            nums[i]=1;	//访问了，状态置为1
            pailie(vec,nums,num);
            vec.pop_back();
            nums[i]=0;	//要记得进行状态回溯
        }
    }
}
void pri_pailie(vector<int> &vec){
    for(int i=0;i<7;i++) printf("%d ",vec[i]);
    printf("%d\n",vec[7]);
}