LeetCode 90. 子集II

题目描述

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

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

题解

回溯算法

代码

// C++
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ret;
    vector<int> temps;
    backtrack(nums, 0, temps, ret);
    return ret;
}
void backtrack(vector<int>& nums, int level, vector<int> temps, vector<vector<int>>& ret) {
    ret.push_back(temps);
    for (auto i = level; i < nums.size(); ++i) {
        if (i > level && nums[i] == nums[i-1]) {
            continue;
        }
        temps.push_back(nums[i]);
        backtrack(nums, i + 1, temps, ret);
        temps.pop_back();
    }
}

迭代法

• 类似于 子集问题迭代法 ，可以将重复数字视为一个元素。
• 每个数字放入子集的可能性取决于这个数字的个数。
• 例如：集合中有 [5,5] ，所以有两种可能 [5], [5, 5]，将这两种可能分别放入之前的所有子集。

代码

// C++
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ret = {{}};
    int size = (int)nums.size();
    for (auto i = 0; i < size;) {
        int n = nums[i];
        int count = 1;
        while (i + count < size && nums[i+count] == n) {
            ++count;
        }
        int retSize = (int)ret.size();
        for (auto j = 0; j < retSize; ++j) {
            auto subnums = ret[j];
            for (auto k = 0; k < count; ++k) {
                subnums.push_back(n);
                ret.push_back(subnums);
            }
        }
        i += count;
    }
    return ret;
}

参考链接

• C++ solution and explanation, LeetCode Discuss.

类似题目

• 子集