LIntcode: Permutations II

Given a list of numbers with duplicate number in it. Find all unique permutations.

Have you met this question in a real interview? 

Yes

Example

For numbers [1,2,2] the unique permutations are:

[

    [1,2,2],

    [2,1,2],

    [2,2,1]

]

Challenge

Do it without recursion.

Tags Expand 

Recursion

Just like combination.
To avoid duplicates, we need to order first, then avoid duplicated in 3 lines 29 - 31

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: /** * @param nums: A list of integers. * @return: A list of unique permutations. */ vector<vector<int> > permuteUnique(vector<int> &nums) { vector<vector<int> > permutations; if(nums.size() == 0) return permutations; vector<int> temvec; vector<bool> isVisited(nums.size(), false); sort(nums.begin(), nums.end()); DFS(isVisited, temvec, permutations, nums); return permutations; } private: void DFS(vector<bool> &isVisited, vector<int> &temvec, vector<vector<int> > &permutations, vector<int> &nums){ if(temvec.size() == nums.size()) { permutations.push_back(temvec); return; } for(int i = 0; i < nums.size(); i++){ if(isVisited[i]) continue; isVisited[i] = true; temvec.push_back(nums[i]); DFS(isVisited, temvec, permutations, nums); temvec.pop_back(); isVisited[i] = false; while((i + 1) < nums.size() && nums[i] == nums[i + 1]){ i++; } } } };