当前位置：首页 > news >正文

算法力扣刷题记录八十四【46.全排列】

news 2025/7/24 5:30:01

前言

回溯章节第11篇。记录八十四【46.全排列】
回溯学习过：组合问题、切割问题、子集问题。
本文是排列问题。

一、题目阅读

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

二、尝试实现

2.1分析题目，确定方法

记录六十三【回溯章节开篇】讲过回溯解决哪些问题。题目直白指出求排列，解决排列用回溯。
确定回溯之后，需要构造一个树形结构。按照树形结构方便实现递归。以示例1为例：
搜集结构都是在叶子节点，所以有终止条件：和子集问题不一样；
可选元素不是在已选元素之后继续选择，和组合不一样。
发现：一个排序需要用到集合所有的元素，需要记录这个元素有没有被选过。所以用used数组表示当前已有的排列中有没有该元素。

2.2回溯思路

确定返回值：用全局变量 vector<vector< int>> result; vector< int> temp; 搜集结果。所以返回值是void。
确定参数：

需要输入集合：const vector< int>& nums；
需要used数组：vector< bool>& used。表示当前已有的排列中有没有该元素。

确定终止条件：当temp.size() == nums.size()，temp中已经是一个排列了。就该return。
确定逻辑：

for循环，从0开始，到nums.size()结束；
如果used == false，说明排列中还没有这个元素，那么可以放入temp并且used改成true；否则，continue；
放入temp之后，递到下一层；
回溯：把元素pop并且used = false。

代码实现【回溯】

class Solution {
public:vector<vector<int>> result;vector<int> temp;void backtracking(const vector<int>& nums,vector<bool>& used){if(temp.size() == nums.size()){result.push_back(temp);return;}for(int i = 0;i < nums.size();i++){if(used[i] == false){temp.push_back(nums[i]);used[i] = true;backtracking(nums,used);temp.pop_back();used[i] = false;}}return;}vector<vector<int>> permute(vector<int>& nums) {result.clear();temp.clear();vector<bool> used(nums.size(),false);//有没有被选到backtracking(nums,used);return result;}
};

三、参考学习

【46.全排列】参考学习链接

参考给的思路和方法与尝试实现中一致。
分析时间复杂度：递归次数 * 每次递归的时间复杂度。

递归次数：第一层for循环可选n个元素，是排列的第一个元素；第二层for循环可选n-1个元素，是排列的第二个元素；第三层for循环可选n-2个元素，是排列的第三个元素……直到最后一个元素。所以一个集合有 n! 个排列。需要递归 n! 次。
每次递归的时间复杂度：操作单元是处理——递归——回溯完整过程。O(1)。
所以时间复杂度是O(n!)。