长沙电信网站备案,互联网,网站做长连接,百度网站建设中心LeetCode 热题 100_两数之和#xff08;55_46#xff09; 题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;递归#xff08;回溯#xff09;#xff09;#xff1a; 代码实现代码实现#xff08;思路一#xff08… LeetCode 热题 100_两数之和55_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 中的所有整数 互不相同
题解
解题思路
思路一递归回溯
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)。
代码实现
代码实现思路一递归回溯
class Solution {
private://用于存放一种排列vectorint path;//用于存放所有全排列vectorvectorint res;//运用回溯算法求解全排列问题void backtracking(vectorintnums,vectorbool 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:vectorvectorint permute(vectorint nums) {//标记元素是否被使用vectorbool used(nums.size(),false);backtracking(nums,used);return res;}
};以思路一为例进行调试
#includeiostream
#includevector
using namespace std;class Solution {
private://用于存放一种排列vectorint path;//用于存放所有全排列vectorvectorint res;//运用回溯算法求解全排列问题void backtracking(vectorintnums,vectorbool 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:vectorvectorint permute(vectorint nums) {//记录元素是否被使用vectorbool used(nums.size(),false);backtracking(nums,used);return res;}
};int main(){vectorint a{1,2,3};//对a中的元素进行全排列Solution s;vectorvectorint resultss.permute(a);//输出全排列的结果for (auto result : results){cout[;for (auto i : result){couti;}cout] ;}return 0;
}LeetCode 热题 100_全排列(55_46)原题链接 欢迎大家和我沟通交流(✿◠‿◠)
