描述
给你一个整数数组 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
这道题目可以使用回溯算法来解决。在回溯算法中，我们需要维护一个路径（path），表示当前已经选了哪些数，以及一个选择列表（choices），表示当前还可以选择哪些数。在每一步中，我们可以选择将一个数加入路径中，或者不将其加入路径中。当路径中的数的个数达到了数组的长度时，我们就得到了一个新的子集。
与“子集”问题不同的是，这道题目中可能包含重复元素，我们需要对重复元素进行去重。具体来说，我们可以先对数组进行排序，然后在回溯算法中，如果当前选择的数与上一个选择的数相同，我们就跳过该选择。
我们可以使用两个函数来解决这个问题。一个函数是 backtrack，它用于搜索所有可能的子集；另一个函数是 subsetsWithDup，它用于初始化回溯算法，并返回所有可能的子集。
在 backtrack 函数中，我们首先将当前路径加入到结果集中。然后，我们遍历当前的选择列表，对于每个选择，我们将其加入到路径中，并递归调用 backtrack 函数。递归完成后，我们需要将该选择从路径中删除，以便进行下一次选择。在遍历选择列表时，如果当前选择的数与上一个选择的数相同，我们就跳过该选择。
在 subsetsWithDup 函数中，我们首先初始化结果集为空集。然后，我们对数组进行排序，并调用 backtrack 函数，得到所有可能的子集，并返回结果集。
C++代码
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
sort(nums.begin(), nums.end()); // 对数组进行排序
backtrack(nums, 0, path, res);
return res;
}
void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
res.push_back(path);
for (int i = start; i < nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复元素
path.push_back(nums[i]);
backtrack(nums, i + 1, path, res);
path.pop_back();
}
}
};
Python代码
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
nums.sort() # 对数组进行排序
self.backtrack(nums, 0, path, res)
return res
def backtrack(self, nums, start, path, res):
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]: continue # 跳过重复元素
path.append(nums[i])
self.backtrack(nums, i + 1, path, res)
path.pop()
