47. Permutations II

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

Example:

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

---

这道题和之前的Permutations很像，只不过此时包含有重复元素。 在Permutations里，我使用了一个一个往里加的思路，今天我使用另一个思路。
为了得到一个序列的所有排列，可以采用每个元素和当前第一个元素交换的思路。比如要得到1,2,3的所有排列，第一轮每个元素和第一个元素交换得到

• 1,2,3
• 2,1,3
• 3,2,1

此时每个元素都有打头的序列出现，再对每一个序列，除掉第一个元素，循环交换。比如对于1,2,3，此时把2,3作为一个新的序列，和此时的第一个元素2交换，得到序列：

• 2,3
• 3,2

然后再和之前的元素1拼接起来，得到以1开头的所有排列：

• 1,2,3
• 1,3,2

同理能得到以2,3打头的所有排列。用这种思路也可以求解Permutations这个题。当遇到有重复元素时，可以先对数组排序，在交换的时候，如果当前元素和前一个元素相同，则不再交换。最后再用set去重，完整代码如下：

class Solution {
public:
    void work(set<vector<int> >& ans, vector<int>& nums, int start)
    {
        if (start == nums.size()) {
            ans.insert(nums);
        }
        else {
            for (int i = start; i < nums.size(); i++) {
                if (i != start && nums[i] == nums[i – 1])
                    continue;
                swap(nums[i], nums[start]);
                work(ans, nums, start + 1);
                swap(nums[i], nums[start]);
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        set<vector<int> > ans;
        work(ans, nums, 0);
        return vector<vector<int> >(ans.begin(), ans.end());
    }
};

本代码提交AC，用时48ms。速度比较慢，应该还有其他更优的算法。

---

新方法，使用和Permutations类似的dfs递归方法，只不过在递归的时候，判断一下，保证这次递归的元素不能和上一次相同。比如数组是[1,1,2]，第一次从第一个1开始递归，那么在这层循环中，下一次递归就不能从第二个1开始了，但是下一层循环中还是应该可以选第二个1的。理解起来有点绕，假设我们把求[1,1,2]的全排列想象成从[1,1,2]中无放回的取数字，依先后顺序扔到3个格子中，每个格子只能放一个数字。那么第一次拿的数可能是1,1,2，则第一次拿第一个1和第二个1产生的全排列应该是完全一样的。

代码如下。第11行：用last记录本次循环中上一个递归的数，那么本次循环不再对同一个数递归了。因为先对数组排序了，所以所有相同的数字都会聚到一起，而且这样产生的全排列是按大小顺序排列的。

class Solution {
private:
    void dfs(const vector<int>& nums, vector<vector<int> >& ans, vector<int>& cand, vector<int>& visited)
    {
        if (cand.size() == nums.size()) {
            ans.push_back(cand);
            return;
        }
        int last = INT_MAX;
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] == 0) {
                if (i != 0 && nums[i] == last)
                    continue; // 不能和上一次递归的元素相同，否则产生冗余排列
                cand.push_back(nums[i]);
                last = nums[i];
                visited[i] = 1;
                dfs(nums, ans, cand, visited);
                visited[i] = 0;
                cand.pop_back();
            }
        }
    }
public:
    vector<vector<int> > permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int> > ans;
        vector<int> cand, visited(nums.size(), 0);
        dfs(nums, ans, cand, visited);
        return ans;
    }
};

本代码提交AC，用时23MS，比前一种方法快，省掉了set去重。

二刷。上述解法固然正确，但是用INT_MAX来初始化last还是有风险的，万一数组中有INT_MAX呢。
更好的方法其实是，不用last记录上一次递归的值，二刷直接在内层if判断，如果i!=0且nums[i]==nums[i-1]，说明这个数和上一个数相同，但是此时还不能continue，万一有[1,1,2]这种情况，在外层递归第二个1时，第一个1在上一轮是已经恢复了visited[0]=0的，所以这里可以加上一个visited[i-1]==0。完整代码如下：

class Solution {
private:
    void dfs(const vector<int>& nums, vector<vector<int> >& ans, vector<int>& cand, vector<int>& visited)
    {
        if (cand.size() == nums.size()) {
            ans.push_back(cand);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] == 0) {
                if (i != 0 && nums[i] == nums[i – 1] && visited[i – 1] == 0)
                    continue;
                cand.push_back(nums[i]);
                visited[i] = 1;
                dfs(nums, ans, cand, visited);
                visited[i] = 0;
                cand.pop_back();
            }
        }
    }
public:
    vector<vector<int> > permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int> > ans;
        vector<int> cand, visited(nums.size(), 0);
        dfs(nums, ans, cand, visited);
        return ans;
    }
};

本代码提交AC，用时23MS。

三刷。判断条件还可以再简单些，用pre记录上次递归的下标即可。

class Solution {
public:
	void dfs(vector<int>& nums, vector<int>& visited, vector<vector<int>>& ans, vector<int>& cur) {
		if (cur.size() == nums.size()) {
			ans.push_back(cur);
			return;
		}
		int pre = -1;
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
				if (pre != -1 && nums[i] == nums[pre])continue;
				visited[i] = 1;
				cur.push_back(nums[i]);
				dfs(nums, visited, ans, cur);
				cur.pop_back();
				visited[i] = 0;
				pre = i;
			}
		}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		vector<int> visited(nums.size(), 0);
		vector<int> cur;
		dfs(nums, visited, ans, cur);
		return ans;
	}
};

本代码提交AC，用时24MS。