90. Subsets II
給定一個可能包含重複元素的整數數組 nums，返回所有可能的子集（即冪集）。
解集不能包含重複的子集。以任意順序返回解集。
範例 1：
輸入：nums = [1,2,2] 輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
Python
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def backtrack(start: int, path: List[int]):
result.append(path[:])
for i in range(start, len(nums)):
# Skip duplicates
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
nums.sort()
result = []
backtrack(0, [])
return result
16.78MB, 43ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
sort(nums.begin(), nums.end());
backtrack(nums, 0, path, result);
return result;
}
private:
void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
result.push_back(path);
for (int i = start; i < nums.size(); ++i) {
if (i > start && nums[i] == nums[i - 1]) {
continue; // Skip duplicates
}
path.push_back(nums[i]);
backtrack(nums, i + 1, path, result);
path.pop_back();
}
}
};
8.5MB, 5ms
Javascript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
let result = [];
let path = [];
// Sort the input to handle duplicates
nums.sort((a, b) => a - b);
const backtrack = (start) => {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
// Skip duplicates
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(i + 1);
path.pop();
}
};
backtrack(0);
return result;
};
54.73MB, 71ms
