输入一组数字(不包含重复数字),输出其所有的排列方式。
样例
输入:[1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]分析:
回溯的经典题
回溯的思路:
时间复杂度分析:
个内部节点,在每个内部节点内均会for循环 n
class Solution {public: vector<vector<int>> res;//结果数组 vector<bool> st;//状态数组 vector<int> path;//保存当前路径的数 vector<vector<int>> permutation(vector<int>& nums) { for(int i=0; i<nums.size(); i++) st.push_back(false); dfs(nums, 0); return res; } void dfs(vector<int>& nums, int u) { if (u == nums.size()) {//u==nums.size()说明当前路径结束,返回一种情况 res.push_back(path); return; } for(int i=0; i<nums.size(); i++) { if(!st[i]) { st[i] = true; path.push_back(nums[i]); dfs(nums, u+1); //从每个分支退回来的时候需要把修改过的状态还原 st[i] = false; path.pop_back(); } } }};输入一组数字(可能包含重复数字),输出其所有的排列方式。
样例
输入:[1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]分析:
由于有重复元素的存在,这道题的枚举顺序和上次不同。
先将所有数从小到大排序,这样相同的数会排在一起;
从左到右依次枚举每个数,每次将它放在一个空位上;
对于相同数,我们人为定序,就可以避免重复计算:我们在dfs时记录一个额外的状态,记录上一个相同数存放的位置 start,我们在枚举当前数时,只枚举
start+1,start+2,…,n这些位置。
不要忘记递归前和回溯时,对状态进行更新。
时间复杂度:
搜索树中最后一层共
class Solution {public: vector<vector<int>> res; vector<int> st, path; vector<vector<int>> permutation(vector<int>& nums) { st = vector<int>(nums.size(), false); sort(nums.begin(), nums.end()); path = vector<int>(nums.size()); dfs(nums, 0, 0); return res; } void dfs(vector<int>& nums, int u, int start) { if(u == nums.size()) { res.push_back(path); return; } if(!u || nums[u] != nums[u-1]) start = 0; for(int i=start;i<nums.size();i++) { if (!st[i]) { st[i] = true; path[i] = nums[u]; dfs(nums, u+1, i+1); // 用st[i]表示path[i]是否存在 // st[i] == false,表示path[i]存在; // st[i] == true,表示path[i]不存在; // 当st[i] == false时,path[i]下次会被新的值覆盖掉,所以就不需要再remove了。 st[i] = false; } } }};另一种解法:
class Solution {public: vector<vector<int>> res; // vector<int> st; vector<int> path; vector<vector<int>> permutation(vector<int>& nums) { // st = vector<int>(nums.size(), false); sort(nums.begin(), nums.end()); // path = vector<int>(nums.size()); path.resize(nums.size()); dfs(nums, 0, 0, 0); return res; } void dfs(vector<int>& nums, int u, int start, int state) { if(u == nums.size()) { res.push_back(path); return; } if(!u|| nums[u] != nums[u-1]) start = 0; for(int i=start;i<nums.size();i++) { if(!(state>>i&1)) { path[i] = nums[u]; dfs(nums, u+1, i+1, state+(1<<i)); } } }};原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。