LeetCode90 子集 II

发表于 | 分类于 |
字数统计: 293 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/subsets-ii/

题意

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

解法

使用回溯来解求子集的问题
通过每次把结果都添加到结果中，然后对于当前位置以后的位置进行回溯递归处理
就可以计算出所有的子集
去重的方法和求全排列类似，是通过排序并判断相同的数是否在当前层已经使用过
如果使用过就跳过

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& nums, vector<int>& temp, int loc) {
        ans.push_back(temp);
        if (loc == nums.size()) {
            return;
        }
        for (int i = loc; i < nums.size(); i++) {
            if (i > loc && nums[i] == nums[i - 1]) continue; // 完成去重
            temp.push_back(nums[i]);
            dfs(nums, temp, i + 1);
            temp.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> temp;
        int n = nums.size();
        dfs(nums, temp, 0);
        return ans;
    }
};