LeetCode 47 Permutations II

    
        标签：
        
            LeetCode
        
            回溯法
        
    发布于：2020-06-11 16:23:16
    编辑于：2021-03-17 22:48:26
    浏览量：1395

https://leetcode.com/problems/permutations-ii/

题目分析

典型的使用回溯法的题目，需要考虑重复数字的情况。

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> nums;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        this->nums = nums;
        vector<int> solution;
        vector<bool> available(nums.size(), true);
        backtrack(available, solution);
        return res;
    }
    
private:
    void backtrack(vector<bool>& available, vector<int>& solution) {
        if(solution.size()==nums.size()) {
            res.push_back(solution);
            return;
        }
        for(int i=0;i<nums.size();i++) {
            if(available[i]) {
                if(i>0&&nums[i-1]==nums[i]&&available[i-1]) continue;
                solution.push_back(nums[i]);
                available[i] = false;
                backtrack(available, solution);
                available[i] = true;
                solution.pop_back();
            }
        }
    }
};

难点在于为什么 if(i>0&&nums[i-1]==nums[i]&&available[i-1]) continue; 是正确的？

例如当输入为 [0, 0, 0, 1, 2] 且第一个 0 未被使用，第二个 0 已被使用，当前我们正在处理第三个 0 时，上述条件为否，也就是说岂不是第一个 0 和第二个 0 都会被用于展开新的分支吗？此时不是将会出现重复解吗？

答案是不会，因为第一个 0 未被使用，第二个 0 已被使用的这种情况根本不会出现。

为什么？ 因为我们是按顺序使用的，当第一个 0 未被使用时，后续的 0 不可能被用到。

Links: LeetCode-47-Permutations-II