94. 递归实现排列型枚举

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• • 题目大意
  • 思路

给定一个数n，输出n的全排列(1 ~ n)

利用深度优先搜索找出所有排列,假设n=3
那么三个空位_ _ _
当第一位填入1 则 变为 1 _ _ 此时state变为001代表第一位数被使用
如上得 第二次 和第三次 分别为 1 2 _ 和 1 2 3 此时三个数被用完u == n 进行输出
而此时再将最后一位添加得数据从容器当中删除,实现回溯在 1 2 3 变为 1 2 _由于此时没有未被使用的数，则再次回溯 变为1 _ _ ，i代表当时添加的是第几位数，所以下一次添加的数将会变为 1 3 _ 最后便是 1 3 2
当1 _ _ 的排列被输出完成后便在回溯为 _ _ _ 状态，此时添加的第一位数为2，state变为 010重复上述步骤

#include
#include
using namespace std;
int n;
vector v;
void dfs(int u,int state)
{
    if(u == n)
    {
        for(auto it : v)
        {
            cout<
       //如果当前数未被选中 
       if(!(state & 1 << i))
       {
       	   // 将当前元素加入容器中
           v.push_back(i + 1);
           dfs(u + 1,state | 1 << i);
           v.pop_back();
       }
    }
}
int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}