LeetCode 面试经典 150_回溯_全排列（100_46_C++_中等）
LeetCode 面试经典 150_回溯_全排列（100_46_C++_中等）
题目描述：
给定一个不含重复数字的数组 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 中的所有整数 互不相同
题解：
解题思路：
思路一（递归（回溯））：
1、这题需求全排列，这里我们可以想到数学上进行全排列的过程。假设求 [1,2,3] 的全排列。我们首先需在[1,2,3] 中，选取一个元素放在第一个位置，再在剩余两个元素中选取一个元素放在第二个位置，再将剩余的一个元素放在最后一个位置 。
例：
⭕代表当前位置选取的元素，[ ]代表可选取元素
通过递归树可以分析出，每层会确定一个元素的位置，从上到下的一条路径正好是一个排列。（在此过程中我们需要记录哪些元素已被选取）
2、具体思路如下：
① 定义一个 used 用来存储当前元素是否被使用。定义一个 path 来存储从上到下的一条路径（正好是一个排列）。定义一个 ans 来存储所有的路径。
② 递归的每层确定一个元素的位置，且每层会列举所有未使用的元素。（每层挑选一个元素（未使用）存入path中，将使用的元素进行标记)。
③ 当path中元素的个数到达全排列的要求时，则将path存入 ans 中，再进行回溯（回溯时需将相应的元素置为未使用）。
3、复杂度分析
① 时间复杂度：O(n * n!)，其中 n 是数组中的元素数量。其主要是递归调用的次数和将path复制到ans中的时间开销。递归调用消耗n！（全排列的个数），每个全排列答案复制到ans中消耗 n 时间 。
② 空间复杂度：O(n)，其中 n 是数组中的元素数量。递归n层（每层确定一个元素的位置）O(n)。path存储从上到下的一条路径（正好是一个排列）O(n)。使用一个used数组存储元素是否被使用O(n)。
代码实现
代码实现（思路一（递归（回溯）））：
classSolution{private://用于存放一种排列 vector<int> path;//用于存放所有全排列 vector<vector<int>> res;//运用回溯算法求解全排列问题voidbacktracking(vector<int>&nums,vector<bool>&used){//递归出口（当path达到一个排列的个数时，也就是到达叶子节点时，记录答案）if(path.size()==nums.size()){ res.emplace_back(path);return;}//在每个位置枚举不用的元素for(int i =0; i < nums.size(); i++){//如果当前元素已经被使用则跳过此元素if(used[i]==true)continue;//若当前元素还未使用，则将其添加到一个排列中，标记已使用 path.emplace_back(nums[i]); used[i]=true;//再重复的添加元素，直到一个排列的个数满足条件backtracking(nums,used);//将当前元素移除切换其他元素，移除后标记为未使用 path.pop_back(); used[i]=false;}}public: vector<vector<int>>permute(vector<int>& nums){//标记元素是否被使用 vector<bool>used(nums.size(),false);backtracking(nums,used);return res;}};以思路一为例进行调试
#include<iostream>#include<vector>usingnamespace std;classSolution{private://用于存放一种排列 vector<int> path;//用于存放所有全排列 vector<vector<int>> res;//运用回溯算法求解全排列问题voidbacktracking(vector<int>&nums,vector<bool>&used){//递归出口（当path达到一个排列的个数时，也就是到达叶子节点时，记录答案）if(path.size()==nums.size()){ res.emplace_back(path);return;}//在每个位置枚举不用的元素for(int i =0; i < nums.size(); i++){//如果当前元素已经被使用则跳过此元素if(used[i]==true)continue;//若当前元素还未使用，则将其添加到一个排列中，标记已使用 path.emplace_back(nums[i]); used[i]=true;//再重复的添加元素，直到一个排列的个数满足条件backtracking(nums,used);//将当前元素移除切换其他元素，移除后标记为未使用 path.pop_back(); used[i]=false;}}public: vector<vector<int>>permute(vector<int>& nums){//记录元素是否被使用 vector<bool>used(nums.size(),false);backtracking(nums,used);return res;}};intmain(){ vector<int> a={1,2,3};//对a中的元素进行全排列 Solution s; vector<vector<int>> results=s.permute(a);//输出全排列的结果for(auto&result : results){ cout<<"[";for(auto&i : result){ cout<<i<<"";} cout<<"] ";}return0;}LeetCode 面试经典 150_回溯_全排列（100_46)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
