全排列
回溯标记法（不去重，时间复杂度高）
在插入之前做一个find查找，找不到相同的插入
class Solution { public: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums , vector<bool>& used) { if(path.size() == nums.size()) { if(find(result.begin() , result.end() , path) == result.end() ) result.push_back(path); return; } for(int i=0 ; i<nums.size() ;i++) { if(used[i] == 1) continue; used[i]=1; path.push_back(nums[i]); backtracking(nums,used); path.pop_back(); used[i]=0; } return; } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<bool> used(nums.size(),false); backtracking(nums,used); return result; } }; 返回该题 力扣 LeetCode
回溯去重
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) { // 此时说明找到了一组 if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { // used[i - 1] == true，说明同一树枝nums[i - 1]使用过 // used[i - 1] == false，说明同一树层nums[i - 1]使用过 // 如果同一树层nums[i - 1]使用过则直接跳过 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) //去重 { continue; } if (used[i] == false) { used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { result.clear(); path.clear(); sort(nums.begin(), nums.end()); // 排序 vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };
树层去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; }
树枝去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) { continue; }
二刷
class Solution { public: vector<vector<int>> result; vector<int> path; vector<bool> underNum; void track_back(vector<int>& nums ) { if(path.size() >= nums.size()) { result.push_back(path); return; } for(int i=0 ; i<nums.size();i++) { if(underNum[i]==true)continue; if(i>0&&nums[i]==nums[i-1]&&underNum[i-1]==false) continue; underNum[i] = true; path.push_back(nums[i]); track_back(nums); path.pop_back(); underNum[i] = false; } return; } vector<vector<int>> permuteUnique(vector<int>& nums) { if(nums.size() == 0 ) return result; sort(nums.begin(),nums.end()); underNum.assign(nums.size(),false); track_back(nums); return result; } };
