Well, have you solved the nextPermutation problem? If so and you have handled the cases of duplicates at that problem, your code can be used in this problem. The idea is fairly simple:
- sort
numsin ascending order, add it tores; - generate the next permutation of
numsusingnextPermutation(), and add it tores; - repeat 2 until the next permutation of
numsreturns to the sorted condition in 1.
The code is as follows. For more about the idea of nextPermutation(), please visit this solution.
1 bool nextPermutation(vector<int>& nums) { 2 int k = -1; 3 for (int i = nums.size() - 2; i >= 0; i--) { 4 if (nums[i] < nums[i + 1]) { 5 k = i; 6 break; 7 } 8 } 9 if (k == -1) { 10 sort(nums.begin(), nums.end()); 11 return false; 12 } 13 int l = -1; 14 for (int i = nums.size() - 1; i > k; i--) { 15 if (nums[i] > nums[k]) { 16 l = i; 17 break; 18 } 19 } 20 swap(nums[k], nums[l]); 21 reverse(nums.begin() + k + 1, nums.end()); 22 return true; 23 } 24 vector<vector<int>> permuteUnique(vector<int>& nums) { 25 vector<vector<int> > res; 26 sort(nums.begin(), nums.end()); 27 res.push_back(nums); 28 while (nextPermutation(nums)) 29 res.push_back(nums); 30 return res; 31 }
Of coruse, this problem is designed for backtracking. You can modify the code in Permutations a little bit to solve this problem. In the following code, an unordered_set is used to prevent duplicates.
1 void permutateUnique(vector<int>& nums, int start, vector<vector<int> >& res) { 2 if (start == nums.size()) { 3 res.push_back(nums); 4 return; 5 } 6 unordered_set<int> st; 7 for (int i = start; i < nums.size(); i++) { 8 if (st.find(nums[i]) != st.end()) continue; 9 st.insert(nums[i]); 10 swap(nums[i], nums[start]); 11 permutateUnique(nums, start + 1, res); 12 swap(nums[i], nums[start]); 13 } 14 } 15 16 vector<vector<int> > permuteUnique(vector<int>& nums) { 17 vector<vector<int> > res; 18 permutateUnique(nums, 0, res); 19 return res; 20 }
You can also sort nums and then use position marks to prevent duplicates, like the following code.
1 void permutateUnique(vector<int> nums, int start, vector<vector<int> >& res) { 2 if (start == nums.size()) { 3 res.push_back(nums); 4 return; 5 } 6 for (int i = start; i < nums.size(); i++) { 7 if (i != start && nums[i] == nums[start]) continue; 8 swap(nums[i], nums[start]); 9 permutateUnique(nums, start + 1, res); 10 } 11 } 12 13 vector<vector<int> > permuteUnique(vector<int>& nums) { 14 sort(nums.begin(), nums.end()); 15 vector<vector<int> > res; 16 permutateUnique(nums, 0, res); 17 return res; 18 }
