给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的 子集
首先，子集问题 就是在回溯时对每个节点进行保存操作
与一般子集问题相比，这个问题中包含重复元素，举个例子，当nums=[1,2,2]，就会出现：
1
/ \
2 2
这样的回溯树，导致添加重复元素
因此要进行树层去重（前提是数组有序）➡ 同一层中，如果i节点与i-1节点相同，跳过
class Solution {
public List<List<Integer>> ans;
public int[] nums;
public void helper(Deque<Integer> path, int startIdx){
ans.add(new ArrayList<>(path));
if(startIdx>=nums.length) return;
for(int i=startIdx; i<nums.length; i++){
path.add(nums[i]);
helper(path, i+1);
path.removeLast();
while(i+1<nums.length && nums[i+1]==nums[i]) i++;
}
return;
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
ans = new ArrayList<>();
this.nums = nums;
helper(new ArrayDeque<>(), 0);
return ans;
}
}
给定
nums，找出并返回所有nums中不同的非递减子序列如： nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
这题也是要去重的，相比于子集2，这题不能预先排序，因此直接相邻的i和i+1判别不现实，如nums= [1,2,1,1]
1 1 （第3个1）
/ \ /
2 1 1
这题是对树根和树层进行去重，而树层去重，可以看作带父节点的树根去重➡每次循环根节点前，增加一个map数组，记录某个节点是否使用过
//nums[i]的值在-100~100之间，用map数组，提高查找时间
class Solution {
public List<List<Integer>> ans;
public int[] nums;
public void dfs(Deque<Integer> path, int startIdx){
if(path.size()>1) ans.add(new ArrayList<>(path));
boolean[] map = new boolean[201];
for(int i=startIdx; i<nums.length; i++){
if(map[nums[i]+100] || (!path.isEmpty() && path.getLast()>nums[i])) continue;
map[nums[i]+100] = true;
path.add(nums[i]);
dfs(path, i+1);
path.removeLast();
}
return;
}
public List<List<Integer>> findSubsequences(int[] nums) {
ans = new ArrayList<>();
this.nums = nums;
dfs(new ArrayDeque<>(), 0);
return ans;
}
}