要没有重复的元素，要保证递归树的每一层元素不重复。这样就需要先排序，然后再执行 dfs 的时候跳过每层重复元素的情况。 Time O(2^n) Space O(n)
⚠️要先排序！
这里有一个讲的很清楚的视频：https://www.youtube.com/watch?v=lCvL8htQ1iI
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) {
return res;
}
List<Integer> cur = new ArrayList<>();
Arrays.sort(nums);
helper(nums, 0, cur, res);
return res;
}
private void helper(int[] nums, int index, List<Integer> cur, List<List<Integer>> res) {
res.add(new ArrayList<>(cur));
for (int i = index; i < nums.length; i++) {
if (i != index && nums[i - 1] == nums[i]) {
continue; // 注意这里去重的处理
}
cur.add(nums[i]);
helper(nums, i + 1, cur, res);
cur.remove(cur.size() - 1);
}
}
}
class Solution:
def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':
nums.sort()
res = []
self.helper(0, nums, [], res)
return res
def helper(self, index, nums, cur, res):
res.append(cur)
for i in range(index, len(nums)):
# skip duplicate
if not (i != index and nums[i - 1] == nums[i]):
self.helper(i + 1, nums, cur + [nums[i]], res)