力扣每日一题90：子集-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣每日一题90：子集。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

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

通过次数

330.7K

提交次数

520.9K

通过率

63.5%

思路和题解

如果说数组里没有重复元素的话，我们可以用回溯法，每次都遍历没有用过的数，对于遍历的数，选择放入这个数字或不放这个数字。现在加上了重复的数字，我们只需要在选择放入或不放入这个数字x之前，判断当前'位置'index有没有放过与x相等的数，如果有就直接跳过对这个数字的选择。

对于判断当前'位置'index有没有放过与x相等的数，我们可以先将数组排序，排序后，相等的数字都相邻，这样就用if(i!=depth&&nums[i]==nums[i-1]) continue;判断是否有重复。文章来源地址https://www.toymoban.com/news/detail-735872.html

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void backtrack(int depth,vector<int> &nums)
    {
        // if(depth>nums.size()) return ;
        ans.emplace_back(temp);
        for(int i=depth;i<nums.size();i++)
        {
            //有重复就跳过这个数字
            if(i!=depth&&nums[i]==nums[i-1]) continue;
            //选择这个数字
            temp.emplace_back(nums[i]);
            backtrack(i+1,nums);
            //不选择这个数字
            temp.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backtrack(0,nums);
        return ans;
    }
};

到了这里，关于力扣每日一题90：子集的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！