【回溯】数字排列问题
<center>
提交: 11 解决: 9
[提交][状态][讨论版] </center>
问题 S: 【回溯】数字排列问题
时间限制: 1 Sec 内存限制: 128 MB提交: 11 解决: 9
[提交][状态][讨论版] </center>
题目描述
列出所有从数字1到数字n的连续自然数的排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入
n（1≤n≤9）
输出
由1~n组成的所有不重复的数字序列，每行一个序列。
样例输入
3
样例输出
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
解题思路：
跟n皇后解法很类似，写递归函数，找好退出条件。
代码：
#include <iostream> #include <cstdio> using namespace std; int n; int a[10]={0}; int yn[10]={0}; void backtrack(int location){ if(location==n+1){ for(int i=1;i<=n;i++){ printf(" %d",a[i]); } printf("\n"); }else{ for(int i=1;i<=n;i++){ if(!yn[i]){ a[location]=i; yn[i]=1; backtrack(location+1); yn[i]=0; } } } } int main() { scanf("%d",&n); backtrack(1); return 0; }
