LeetCode #47：Permutations II(全排列II)

题目描述

本题基于 LeetCode #46 的基础上进行修改即可，与 LeetCode #39 到 LeetCode #40 的修改方法十分类似，均为在原问题的基础上增加了去重。

下面先给出 LeetCode #46 的代码。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {

        used = vector<bool>(nums.size(), false);
        dfs(0, nums);

        return res;
    }

    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;

    void dfs(int depth, vector<int> &nums) {
        if(depth == nums.size()) {
            res.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++) {
            if(!used[i]) {
                path.push_back(nums[i]);
                used[i] = true;
                dfs(depth + 1, nums);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};

LeetCode #46 保证了 nums 数组中每一个元素均不相同，所以我们仿照图的 DFS 就较为容易的写出了代码。唯一的区别就是当前递归层级退出后，需要将 path 的最后一个元素弹出、同时将这个元素标记为未使用的状态，以便进入另一个分支进行搜索（否则按图的 DFS 的运行过程，在最深的层级算法就直接结束了）。

然而 LeetCode #47 的 nums 数组是有重复元素的，如果还是用 #46 的代码，就会出现一些重复的解。我们不妨参考 LeetCode #40 的去重原则——同一递归层级不出现相同的元素、不同的递归层级可以出现相同的元素。在本问题中，我们同样需要先对 nums 数组进行排序，随后，同一递归层级出现相同元素的情况可写为 nums[i] == nums[i - 1]（当然这里天生要保证 i 至少为 1），在这种情况下，若 nums[i - 1] 没有使用过（即 used[i - 1] 为 false），那么 nums[i] 的下一层递归就必然会重新访问 nums[i - 1]——然而这种情况已经在之前出现过了，即排列 (..., nums[i - 1], nums[i], ...) 与 (..., nums[i], nums[i - 1], ...) 最终都会被认为是答案，但 nums[i] 与 nums[i - 1] 是相等的，这种情况显然应该排除。

最终剪枝的代码如下。

if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
    continue;

将 nums 数组从小到大排序，再将剪枝的代码插入到 #46 的 for 循环开头，得到最终 #47 的答案如下。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {

        sort(nums.begin(), nums.end()); // 修改处1：从小到大排序
        used = vector<bool>(nums.size(), false);
        dfs(0, nums);

        return res;
    }

    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;

    void dfs(int depth, vector<int> &nums) {
        if(depth == nums.size()) {
            res.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++) {
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) // 修改处2：剪枝
                continue;
            if(!used[i]) {
                path.push_back(nums[i]);
                used[i] = true;
                dfs(depth + 1, nums);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};