JustSong Archive Link About
Projects
Categories
Others

LeetCode 47 Permutations II

Tag: LeetCode 回溯法 Posted on 2020-06-11 16:23:16 Edited on 2020-06-11 16:26:38 Views: 129

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 不可能被用到。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/