php网页制作代码,网站设计优化方案,wordpress 小程序投稿,尚层装饰公司官网给定一个整数 nn#xff0c;将数字 1∼n1∼n 排成一排#xff0c;将会有很多种排列方法。
现在#xff0c;请你按照字典序将所有的排列方法输出。
输入格式
共一行#xff0c;包含一个整数 nn。
输出格式
按字典序输出所有排列方案#xff0c;每个方案占一行。
数据…给定一个整数 nn将数字 1∼n1∼n 排成一排将会有很多种排列方法。
现在请你按照字典序将所有的排列方法输出。
输入格式
共一行包含一个整数 nn。
输出格式
按字典序输出所有排列方案每个方案占一行。
数据范围
1≤n≤71≤n≤7
输入样例
3输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1难度简单时/空限制1s / 64MB总通过数95837总尝试数121097来源模板题算法标签
思路
1.深度优先搜索只要所有数字使用完成就输出该种情况 if(un){for(int i1;in;i) printf(%d ,path[i]);printf(\n);return;}
2.path[i]表示一条路径每一个位置可以放置一个数字
3.恢复现场改变路径上面的数字数字的使用状态数字被使用之后标记为true ,递归到下一个数字然后恢复现场把路径上面的数字恢复为0其实不恢复也没关系因为下一次使用赋值会直接覆盖原来的数字把数字的使用状态恢复为未使用false for(int i1;in;i){if(!state[i]){path[u]i;state[i]true;dfs(u1);path[u]0;state[i]false;}}
代码
#includeiostream
using namespace std;const int N10;
int n,path[N];
bool state[N];void dfs(int u)
{if(un){for(int i1;in;i) printf(%d ,path[i]);printf(\n);return;}for(int i1;in;i){if(!state[i]){path[u]i;state[i]true;dfs(u1);path[u]0;state[i]false;}}
}int main()
{scanf(%d,n);dfs(1);return 0;
}
