# 0090. 子集 II

## 题目地址(90. 子集 II)

<https://leetcode-cn.com/problems/subsets-ii/>

## 题目描述

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

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

示例:

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

## 前置知识

* [回溯](https://github.com/azl397985856/leetcode/blob/master/thinkings/backtrack.md)

## 公司

* 阿里
* 腾讯
* 百度
* 字节

## 思路

回溯的基本思路清参考上方的回溯专题。

这道题需要求子集，因此首先我们需要在所有的节点都执行加入结果集的操作，而不是像全排列那样在叶子节点才执行。

另外一个需要注意的是本题是包含重复元素的。以题目中的 \[1,2,2] 为例，第一个 2 和第二个 2 是没有区别的。也就是说交换两者的位置也仅算一种情况，而不是多个。

如果是 \[1,2,2,2,2,2] 呢？如果还是以 78 题的逻辑来做会有很多重复结果，那么我们如何避免上面的重复计算？

一种可行的方式是先排序，排序之后规定一种**针对相邻且相等的情况的取数逻辑**，使得无论多少个相邻的同样数字**仅有一种取法**。

而这个取数逻辑其实很简单，那就是**i > start && nums\[i] === nums\[i - 1]**，其中 i 为当前遍历的索引， start 为遍历的起始索引。（大家可以结合上面的回溯专题的图来理解）

## 关键点解析

* 回溯法
* backtrack 解题公式

## 代码

* 语言支持：JS，C++，Python3

JavaScript Code：

```javascript
function backtrack(list, tempList, nums, start) {
  list.push([...tempList]);
  for (let i = start; i < nums.length; i++) {
    // 和78.subsets的区别在于这道题nums可以有重复
    // 因此需要过滤这种情况
    if (i > start && nums[i] === nums[i - 1]) continue;
    tempList.push(nums[i]);
    backtrack(list, tempList, nums, i + 1);
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  const list = [];
  backtrack(
    list,
    [],
    nums.sort((a, b) => a - b),
    0,
    []
  );
  return list;
};
```

C++ Code：

```cpp
class Solution {
private:
    void subsetsWithDup(vector<int>& nums, size_t start, vector<int>& tmp, vector<vector<int>>& res) {
        res.push_back(tmp);
        for (auto i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            tmp.push_back(nums[i]);
            subsetsWithDup(nums, i + 1, tmp, res);
            tmp.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        auto tmp = vector<int>();
        auto res = vector<vector<int>>();
        sort(nums.begin(), nums.end());
        subsetsWithDup(nums, 0, tmp, res);
        return res;
    }
};
```

Python Code:

```python
class Solution:
    def subsetsWithDup(self, nums: List[int], sorted: bool=False) -> List[List[int]]:
        """回溯法，通过排序参数避免重复排序"""
        if not nums:
            return [[]]
        elif len(nums) == 1:
            return [[], nums]
        else:
            # 先排序，以便去重
            # 注意，这道题排序花的时间比较多
            # 因此，增加一个参数，使后续过程不用重复排序，可以大幅提高时间效率
            if not sorted:
                nums.sort()
            # 回溯法
            pre_lists = self.subsetsWithDup(nums[:-1], sorted=True)
            all_lists = [i+[nums[-1]] for i in pre_lists] + pre_lists
            # 去重
            result = []
            for i in all_lists:
                if i not in result:
                    result.append(i)
            return result
```

## 相关题目

* [39.combination-sum](/leetcode-solution/medium/39.combination-sum.md)
* [40.combination-sum-ii](/leetcode-solution/medium/40.combination-sum-ii.md)
* [46.permutations](/leetcode-solution/medium/46.permutations.md)
* [47.permutations-ii](/leetcode-solution/medium/47.permutations-ii.md)
* [78.subsets](/leetcode-solution/medium/78.subsets.md)
* [113.path-sum-ii](/leetcode-solution/medium/113.path-sum-ii.md)
* [131.palindrome-partitioning](/leetcode-solution/medium/131.palindrome-partitioning.md)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/90.subsets-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.