Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]这一题和上一题类似，就是数组里有重复的元素。
思路：递归+深度优先搜索
利用标记信息，加一个判断条件，将重复元素去除
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ans; vector<int> cur; vector<bool> mark(nums.size(), false); sort(nums.begin(), nums.end()); dfs(nums, 0, ans, cur, mark); return ans; } void dfs(vector<int>& nums, int num, vector<vector<int >>& ans, vector<int>& cur, vector<bool>& mark) { if (num == nums.size()) {//排完了，存入 ans.push_back(cur); } for (int i = 0; i < nums.size(); i++) { if (mark[i] || i > 0 && nums[i] == nums[i - 1] && !mark[i - 1]) continue; cur.push_back(nums[i]); mark[i] = true; dfs(nums, num + 1, ans, cur, mark); cur.pop_back();//回溯 mark[i] = false; } } };