Leetcode47.全排列II

题目描述:

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

思路

排列的问题就用回溯。
由于nums数组中可能有相同的数字,所以在全排列时会出现重复的排列。这就需要剪枝。思路如下:
首先将nums数组进行排序,让相同的数字紧邻;
然后在递归填入数字的过程中每次都需要遍历vis数组来查找未被使用过的数字,这样我们只寻找未被使用的数字中的第一个,例如nums = [1, 1, 2],当第一个1开头的所有排列情况都被找到后,开始寻找第二个1开头的排列,这时的vis = [0, 0, 0],表示三个数字都未被使用,但是对于第2个1来说,前一个数字和它相同却未被使用,说明这种情况之前出现过,可以直接continue跳过。剪枝的代码为:

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
	//剪枝,避免填入这个位置曾经填入过的数字
    continue;
}

题解:

class Solution {
    vector<bool> vis;
public:
    void backtrace(int idx, vector<int>& tmp, vector<vector<int>>& ans, vector<int>& nums) {
        if (idx == nums.size()) {	//idx与size相等,说明已经填完了所有的数字,此时的tmp存储的是一个
        							//合法答案,将其加入ans数组,并返回。
            ans.emplace_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
            	//剪枝,避免填入这个位置曾经填入过的数字
                continue;
            }
            if (!vis[i]) {
                tmp.emplace_back(nums[i]);
                vis[i] = 1;
                backtrace(idx + 1, tmp, ans, nums);
                vis[i] = 0;
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> tmp;
        backtrace(0, tmp, ans, nums);
        return ans;
    }
};
上一篇:Codeforces Round #749 (Div.1+Div.2)A-D题解


下一篇:hdu 7136 Jumping Monkey (并查集,重构树)