LintCode(16) 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.

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 35 36

class Solution { public: /** * @param nums: A list of integers. * @return: A list of unique permutations. */ vector<vector<int> > permuteUnique(vector<int> &nums) { // write your code here vector<vector<int>> result; vector<int> solution; if (nums.empty()) return result; vector<bool> visited(nums.size(),false); sort(nums.begin(),nums.end()); dfs(nums,result,solution, visited); return result; } void dfs(vector<int>& nums, vector<vector<int>>&result, vector<int>& solution, vector<bool>& visited){ if (solution.size()==nums.size()){ result.push_back(solution); return; } for (int i=0; i<nums.size(); i++){ if (visited[i]) continue; visited[i]=true; solution.push_back(nums[i]); dfs(nums,result, solution, visited); solution.pop_back(); visited[i]=false; while(nums[i]==nums[i+1]) i++; } } };