LeetCode [47] Permutations II

47. Permutations II

Medium

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

 

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ret; sort(nums.begin(), nums.end()); bt(nums, ret, 0, nums.size()); return ret; } //nums cannot be reference so that nums[pos+1..n-1] is in increasing order void bt(vector<int> nums, vector<vector<int>> &ret, int pos, int n){ if(pos==n){ ret.push_back(nums); }else{ for(int i=pos; i<n; ++i){ if(i>pos && nums[i]==nums[pos]) continue; swap(nums[pos], nums[i]); bt(nums, ret, pos+1, n); //cannot swap back; otherwise nums[pos+1..n-1] will not be in increasing order } } } };

=========== 

Note
It is important to keep the increasing order of the non-determined portion of the vector, ie., nums[pos+1, n-1], such that we can conveniently skip the duplicate cases by line 17.

An example for the recursion of nums. pos=0. Note that nums[1, 4] are in increasing order.
0 1 2 3 4 -- index
1 2 3 4 5
2 1 3 4 5
3 1 2 4 5
4 1 2 3 5
5 1 2 3 4

If nums is swapped back at line20. nums[1, 4] are no longer in increasing order.
0 1 2 3 4 -- index
1 2 3 4 5
2 1 3 4 5
3 2 1 4 5
4 2 3 1 5
5 2 3 4 1