Well, have you solved the nextPermutation problem? If so, 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.
A final note, the following code can be applied to the problem of Permutations II without any modification since the cases of duplicates have already been handled in nextPermutation(). If you want to learn more about 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>> permute(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 course, you are supposed to use the backtracking idea. A simple code is as follows.
1 void permutate(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 swap(nums[i], nums[start]); 8 permutate(nums, start + 1, res); 9 } 10 } 11 12 vector<vector<int> > permute(vector<int>& nums) { 13 vector<vector<int> > res; 14 permutate(nums, 0, res); 15 return res; 16 }
