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.

和上题一样，需要backtracking来做，上题的剪枝用的是记忆化搜索来查找是否已经被visited过了，这题如果画树状图的话，会发现和permutation一样， 需要放弃掉相同元素的出去第一个的其他元素（参考permutations II). 所以会看到在剪枝的时候用到 visited[i] 来确保当前元素是第一次出现在解里面，

这里有个很绕的地方， 做题的时候想了好久。。。

 同时加了另外一个条件 i>0 && nums[i]==nums[i-1] && !visited[i-1] 来保证每一层不会出现重复的数字。 这个逻辑挺绕的，就是在第k个位置，如果我们有2， 2 连续两个数字，那么第一个2肯定没问题，第2个2我们是不能选的，那么如何排除呢，首先他和第一个2比是重复元素， 但是这里不能就直接丢掉，因为这里丢掉的话，当我们有一个(1,2)<2的解得情况下，也会把这个2丢掉， 这个时候比较tricky就是如果第一个2出现在第k层以前，那么他一定会把visited mark为true, 那么我们还是需要第二个2的， 我们知道第一个2按照顺序遍历，一定会先出现我们的解里面，但是回溯完以后，我们会把他visited设为false....这个好绕啊。。。但是！visited[i-1]就是从这里来的，意思为，这个数在同一层出现过一次了，不要了。

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

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; if (nums.empty()) return result; sort(nums.begin(),nums.end()); vector<int> solution; vector<bool> visited(nums.size(), false); dfs(result, solution, nums, 0, visited); } void dfs(vector< vector<int> >& result, vector<int>& solution, vector<int>& nums, int level, vector<bool>& visited){ if (level == nums.size()){ result.push_back(solution); return; } for (int i=0; i<nums.size(); i++){ if (visited[i] || i>0 && nums[i]==nums[i-1] && !visited[i-1] ) continue; solution.push_back(nums[i]); visited[i]=true; dfs(result, solution, nums, level+1,visited); solution.pop_back(); visited[i]=false; } } };

其实，如果不想太绕的话，总用第一个出现的元素更新，就是不管哪一层都用第一个元素就够用了。所以在dfs后，可以把所有后面重复的元素都剪掉。 这个反而更好理解一些，见代码。。。。

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 37

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; if (nums.empty()) return result; sort(nums.begin(),nums.end()); vector<int> solution; vector<bool> visited(nums.size(), false); dfs(result, solution, nums, 0, visited); } void dfs(vector< vector<int> >& result, vector<int>& solution, vector<int>& nums, int level, vector<bool>& visited){ if (level == nums.size()){ result.push_back(solution); return; } for (int i=0; i<nums.size(); i++){ if (visited[i] ) continue; solution.push_back(nums[i]); visited[i]=true; dfs(result, solution, nums, level+1,visited); solution.pop_back(); visited[i]=false; while(i<nums.size()-1&& nums[i+1]==nums[i]) i++; } } };