47. 全排列 II

自己做

解1：檢查重復

class Solution {
public:void circle(vector<int> nums, vector<vector<int>> &res,int start){int len = nums.size();if(start == len - 1){                       //到頭了//檢查重復bool is_exist = false;for(int i = 0; i < res.size(); i++){bool same = true;                   //標記是否相同for(int j = 0; j < res[0].size(); j++)if(nums[j] != res[i][j]){          //不相同same = false;break;}if(same){                           //出現了相同is_exist = true;                //標記重復break;}}if(!is_exist)res.push_back(nums);                    //加入結果中return;}for(int i = start; i < len; i++){if(i == start || nums[i] != nums[start]){swap(nums[i], nums[start]);             //交換circle(nums, res, start + 1);           //進入下一層循環swap(nums[i], nums[start]);             //歸位}}}vector<vector<int>> permuteUnique(vector<int>& nums) {int len = nums.size();vector<vector<int>> res;circle(nums, res, 0);return res;}
};

看題解

官方代碼：

首先通過排序將重復元素全部堆一起

判斷條件中

vis[i]?表示該元素是否被取過

i > 0 && nums[i] == nums[i - 1] && !vis[i - 1] 表示該元素是否與上個元素相同，如果相同并且上個元素沒取過則取該元素

class Solution {vector<int> vis;public:void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {if (idx == nums.size()) {ans.emplace_back(perm);return;}for (int i = 0; i < (int)nums.size(); ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}perm.emplace_back(nums[i]);vis[i] = 1;backtrack(nums, ans, idx + 1, perm);vis[i] = 0;perm.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> ans;vector<int> perm;vis.resize(nums.size());sort(nums.begin(), nums.end());backtrack(nums, ans, 0, perm);return ans;}
};