【排列问题】

问题：

已知某序列有n个元素，请编写程序打印出包含该序列所有元素的所有排列。

输入要求： 输入第1行为整数n，表示该序列元素的个数；第2行为n个整数，表示需要排列的序列元素。 

输出要求：输出若干行，每一行为包含序列所有元素的一种排列。

思路：

兄弟结点不重复，父子关系可重复

代码（中间的错误代码，但无法理解输出的产生）：

#include<bits/stdc++.h>
using namespace std;char element[110];
int sign[110];void dfs(int cnt, int n, string work)
{if(cnt > n){cout << work << endl;}for(int i = 1; i <= n; i++){if(sign[i]) continue;sign[i] = 1;work += element[i];dfs(cnt+1, n, work);sign[i] = 0;}
}
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++){cin >> element[i];}sort(element+1, element+n+1);dfs(1, n, "");return 0;
}

#include<bits/stdc++.h>
using namespace std;char element[110];
int sign[110];void dfs(int cnt, int n, string work)
{if(cnt > n){cout << work << endl;}int element_mark[210];for(int i = 1; i <= n; i++){if(sign[i] || element_mark[element[i]] == cnt) continue;sign[i] = 1;element_mark[element[i]] = cnt;string temp = work;work += element[i];dfs(cnt+1, n, work);work = temp;sign[i] = 0;}
}
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++){cin >> element[i];}sort(element+1, element+n+1);dfs(1, n, "");return 0;
}

正确代码：

#include<bits/stdc++.h>
using namespace std;char element[110];
int sign[110];void dfs(int cnt, int n, string work)
{if(cnt > n){cout << work << endl;}int element_mark[210] = {0};for(int i = 1; i <= n; i++){if(sign[i] || element_mark[element[i]] == cnt) continue;sign[i] = 1;element_mark[element[i]] = cnt;string temp = work;work += element[i];dfs(cnt+1, n, work);work = temp;sign[i] = 0;}
}
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++){cin >> element[i];}sort(element+1, element+n+1);dfs(1, n, "");return 0;
}

感想：

要用解空间树来思考约束，要用搜索空间树来修改约束