题目心得

一般的DFS问题思路不难，重点是理解代码实现的过程，共勉!

C++ 代码

#include <iostream>
using namespace std;

const int N = 10;

int n;          //n设为全局变量, perm()可以省略一个形参
int a[N];       //记录各个位置的数字
bool flag[N];   //记录某个数字是否已被用过

void perm(int u) {
    if(u > n) {       //最后一个位置插入后输出
        for(int i = 1; i <= n; i++) 
            cout << a[i] << " ";
        cout << endl; //换行   
        return;       //函数执行结束
    }
    //从数字1到n开始遍历
    for(int i = 1; i <= n; i++) {
        if(!flag[i]) {      //数字i未被用过
            a[u] = i;       //记录当前位置数字
            flag[i] = true; //标记置为true(表示数字i已被用过)
            perm(u + 1);    //递归下一个位置
            flag[i] = false;//回溯(恢复现场)
            //由于a[u]在递归过程中会被覆盖,所以不用写a[u]=0
        }
    }

}

int main() {
    cin >> n;
    perm(1);    //从第一个位置开始
    return 0;
}