Permutations II

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

http://www.lintcode.com/en/problem/permutations-ii/

Discussion

有重复元素的排列问题。

最简单的办法是对Permutation的结果去重就可以了。结果去重的问题在3 Sum问题里也遇到过了。对Permutation的结果进行去重操作：

    sort(result.begin(), result.end());
    vector<vector<int> >::iterator it = unique(result.begin(), result.end());
    result.resize(it-result.begin());//or result.erase(it, result.end());

当然这样会有重复计算问题，虽然没有增加时间复杂度。更好的办法是修改backtracing算法，或者是修改递归终止条件：只有在跟上一个solution不同的时候才会把新的solution记录下来，这样做每次都要比较n次，而产生solution的操作并没有受到影响，所以还是会重复计算；

或者是修改backtracing终点的第二部分：在每一维上枚举candidate number的时候，该number不但不能被枚举过, 而且还要跟上次出现在该维度上的number不同。比如“1 1 2”，solution[0]为1的时候下一个1就不用再放到第0维上了。

Solution

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;
        int n = nums.size();
        if(n == 0) return result;
        vector<int> solution(n, 0);
        vector<bool> used(n, false);
        sort(nums.begin(), nums.end());
        backtracing(nums, 0, result, solution, used);
        return result;
    }
private:
    void backtracing(vector<int> &nums, int dim, vector<vector<int> > &records,
        vector<int> &solution, vector<bool> &used) {
            int n = nums.size();
            if(dim == n) {
                records.push_back(solution);
                return;
            }
            int lastnum = INT_MAX;
            for(int i = 0; i<n; i++) {
                if(used[i] == true) continue;
                if(nums[i] == lastnum) continue;//修改枚举条件，跟上次不同的时候才会记录到solution里
                lastnum = nums[i];
                solution[dim] = nums[i];
                used[i] = true;
                backtracing(nums, dim+1, records, solution, used);
                used[i] = false;
            }
        }
};

起始lastnum初始化为INT_MAX是有问题的，test case没有测出来。应该初始化为num[0]-1；这样就能保证lastnum一开始跟任意个都不同了（已经排序）。

DFS solution. 改造Subsets II问题模板。

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;
        vector<int> path;
        vector<int> state(nums.size(), false);
        sort(nums.begin(), nums.end());
        dfs(nums, result, path, state);
        return result;
    }
    void dfs(vector<int> &nums,  vector<vector<int> > &records, 
    vector<int> &path, vector<int> &state) {
        int n = nums.size();
        if(path.size() == n) {
            records.push_back(path);
            return;
        }
        for(int i=0; i<n; i++) {
            if(state[i] == true) continue;
            if(i!=0 && nums[i] == nums[i-1] && state[i-1]==false) continue;
            //这里刚开始漏掉了state[i-1]==false
            state[i] = true;
            path.push_back(nums[i]);
            dfs(nums, records, path, state);
            path.pop_back();
            state[i] = false;
        }
    }
};

Solution 3

基于交换。去重有技巧。

1. num[i] == num[pos] - 是跟pos去比，因为这决定了还要不要swap
2. 不能引用传递num，然后两次swap，这样的num再到下一层的时候总是有序的，这样就没法去重了。
3. https://leetcode.com/discuss/25279/a-simple-c-solution-in-only-20-lines

class Solution {
public:
    void recursion(vector<int> num, int pos, vector<vector<int> > &res) {
        if (pos == num.size()) {
            res.push_back(num);
            return;
        }
        for (int i = pos; i < num.size(); i++) {
            if (i != pos && num[i] == num[pos]) continue;
            swap(num[i], num[pos]);//这里的swap只影响当前recursion，因为num不是引用传递
            recursion(num, pos+1, res);
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >res;
        recursion(num, 0, res);
        return res;
    }
};