842. 排列数字(acwing)

本文主要是介绍842. 排列数字(acwing)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

842. 排列数字

题目描述

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

回溯算法（dfs）

// 引入所有标准库
#include<bits/stdc++.h>
using namespace std;// 全局变量声明
// nums: 存储1至n的所有数字
vector<int> nums;
// path: 存储当前路径（部分排列）
vector<int> path;
// used: 标记已经使用过的数字
vector<bool> used(10,false);
// n: 数字的范围和排列长度
int n;// 回溯函数，用于生成排列
void backtracking(vector<int>& nums, int start)
{// 如果当前路径的长度等于n，说明找到了一个完整的排列if(path.size() == n){// 打印当前找到的排列for(int i = 0; i < path.size(); i++){cout << path[i] << " ";}cout << "\n";// 返回上一层递归return;}// 遍历nums中的所有数字for(int i = 0; i < nums.size(); i++){// 检查当前数字是否已经被使用if(!used[i]){// 如果没有被使用，则添加到当前路径path.push_back(nums[i]);// 标记该数字为已使用used[i] = true;// 继续递归填充下一个数字backtracking(nums, i);// 回溯，将最后一个数字从路径中移除，并标记为未使用path.pop_back();used[i] = false;}}// 当前分支结束，返回上一层递归return;
}// 主函数
int main()
{// 输入数字范围cin >> n;// 初始化nums数组，放入1至n的数字for(int i = 1; i <= n; i++)nums.push_back(i);// 调用回溯函数，生成所有排列backtracking(nums, 0);// 正常结束程序return 0;
}

这个程序是一个简单的排列生成器，使用深度优先搜索和回溯来生成所有可能的数字排列。注意到程序没有处理 start 参数，这是因为它在这个特定的实现中没有用到。程序是根据数字是否已经被使用来决定下一步的递归，而不是基于当前的递归深度或位置，因此即便这个参数被传递到函数，它也不会被使用。

此外，由于数据范围限制为 1≤n≤7，所以 used 数组的大小被硬编码为10，足够容纳所有可能的输入。在更通用的实现中，这个大小应该是根据输入动态调整的。

这篇关于842. 排列数字(acwing)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---