/*************************************************************************

	> File Name: sort_card_dfs.cpp

	> Author:

	> Mail:

	> Created Time: 2015年11月12日 星期四 09时35分50秒

 ************************************************************************/

#include<iostream>

using namespace std;

const int MAXNUM = 100;

int num;//要排序数字的个数

int box[MAXNUM];//用来表示排序情况的数组

int book[MAXNUM];//标记已经放下的数字

void dfs(int step)

{

    if (step == num+1){//把所有的数字都放完了之后，就要将此排列输出；

        for (int i = 1; i <= num; i++){

            cout << box[i] << " ";

        }

        cout << endl;

        return;//其实没有也行，但是没有话程序还要执行下面的循环再返回

    }

		/*

			从num个数字中选择第一个没有放下的数字，然后把它放下（标记为1）；

		*/

    for (int i = 1; i <= num; i++){

        if (book[i] == 0){

            box[step] = i;

            book[i] = 1;

            dfs(step+1);

            book[i] = 0;//将之前放下的数字取走（标记为0）；用于下次排列放入；

        }

    }

}

int main()

{

    cout << "Input the n: ";

    cin >> num;

    dfs(1);

    return 0;

}