47. 全排列 II

力扣链接(中等)：https://leetcode.cn/problems/permutations-ii

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

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

个人题解

• 注意排列和组合两类问题在 for 循环开始位置的区别；
• 注意去重方式和组合总和 II的异同。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(vector<int> &nums, vector<bool> &used) {
        if(path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++) {
            // 排除单条路径中已经取过的值
            if(used[i]) continue;
            // 这里的去重方式和 「组合总和 II」 写法不同，但原理是一样的
            // !used[i - 1] 的作用是排除上一次 for 中由于 used[i] == true 导致被跳过的情况
            // 如果 nums[i - 1] 在当前遍历路径上被使用，那么 used[i - 1] == true 就会被上一次 for continue 掉
            // 那么此时很显然即便满足 i && nums[i] == nums[i - 1]，逻辑也是不对的，因为上一个元素都被 continue 了
            // 自然不存在所谓的层内重复，更好的方式是画一个树形图走一遍过程
            // 可以和 「组合总和 II」中 i > begin 的思想类比一下
            if(i && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // 首先排序，才能让相同元素相邻，判断和前一个数是否相等即可
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};