# 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](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/39.combination-sum)
* [40.combination-sum-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/40.combination-sum-ii)
* [46.permutations](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/46.permutations)
* [47.permutations-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/47.permutations-ii)
* [78.subsets](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/78.subsets)
* [113.path-sum-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/113.path-sum-ii)
* [131.palindrome-partitioning](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/131.palindrome-partitioning)