全排列问题

// 全排列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
解题：
1、递归式：填好怕p[1]~p[index - 1]，准备填index，显然需要枚举1_{n，如果当前枚举数字没有再P[1]}P[INDEX - 1]中，就将其填入index，并且hash置为true，然后去处理Index+1，当递归完成后，将hash[index]还原为false；
2、递归边界就是 n + 1；

learn && wrong:
1、最强其实是for+递归+hash
2、很难写其实...

*/

#include <iostream>
using namespace std;

const int maxn = 11;

//P为当前排列，hashtable记录整数x是否已经在P中
int n, p[maxn], hashtable[maxn] = { false };

//当前处理排列的第index位
void generatep(int index) {
    if (index == n + 1) {
        for (int i = 1;i <= n;++i) { //递归边界，已处理完1 ~ n位
            printf("%d", p[i]); //输出当前排列
        }
    }
    printf("\n");
    return;

    for (int x = 1;x <= n;x++) {  //枚举1~n，试图将x填入p[index]
        if (hashtable[x] == false) { //如果x不在p[0]~p[index - 1],
            p[index] = x;  //令p的index位为x，即把x加入P
            hashtable[x] = true; //标记x已经在队列中
            generatep(index + 1); //递归处理下一位
            hashtable[x] = false; //已经处理完p[index]为x的子问题，还原状态
        }
    }
}

int main()
{
    n = 3;
    generatep(1);
    return 0;
}