#leetcode刷题之路47-全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

之前的https://www.cnblogs.com/biat/p/10667051.html加个判断就行了

void backtracking(vector<int>& nums,int start,vector<int> &temp,vector<vector<int>> &ans) {

    if (!nums.size()) return;

    if (start>=nums.size())

    {

        if(find(ans.begin(),ans.end(),temp)==ans.end())

        ans.push_back(temp);

        return;

    }

    for (int i=start; i<nums.size();i++)

    {

        swap(nums[i],nums[start]);

        temp.push_back(nums[start]);

        backtracking(nums, start+, temp,ans);// 递归求解

        temp.pop_back();//回溯,不影响此次的循环

        swap(nums[i], nums[start]);//回溯不影响此次的循环

    }

}

vector<vector<int>> permuteUnique(vector<int>& nums) {

    vector<vector<int>> ans;

    vector<int> curSeq;

    backtracking(nums, , curSeq,ans);

    return ans;

}

借鉴@宝宝可乖了一个方法：

  vector<vector<int>> permuteUnique(vector<int>& nums) {

        sort(nums.begin(), nums.end());

        perm(nums, , nums.size() - );

        return ans;

    }

    void perm(vector<int> nums, int left, int right) {

        if (left == right)

            ans.push_back(nums);

        else {

            for (int i = left; i <= right; i++) {

                if (i != left && nums[left] == nums[i]) continue;  # 去重

                swap(nums[left], nums[i]);

                perm(nums, left + , right);

            }

        }

    }

“其实这个全排列算法就是固定一个数的位置(left)，然后从下一位数再开始全排列(递归过程)...直到最后一位数，模拟手动全排列的过程。所以如果要去重的话，只要控制每次排列时，固定的那个数是不一样的就行了。因为固定的数不一样，那从这个数开始产生的全排列就不一样。所以只要让每次的left位置的数不一样就行，所以先sort，保证只有相邻的数是可能一样的，然后if (i != left && nums[left] == nums[i]) continue;使得每次固定的数(即left)都不一样，就行了。希望能解答你的疑问”

巴特西

#leetcode刷题之路47-全排列 II

最新文章

热门文章