LeetCode 78-子集Ⅱ
class Solution {
//存储返回结果的集合
List<List<Integer>> rs = new ArrayList<>();
//存储子集的临时数组
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
backTracking(nums, 0);
//去重复操作
List<List<Integer>> rs1 = new ArrayList<>();
for(List<Integer> list: rs){
//对集合中的每一个子集进行排序，为后续去重复做基础
Collections.sort(list);
//去重复操作
if(!rs1.contains(list)){
rs1.add(list);
}
}
return rs1;
}
void backTracking(int[] nums, int startIdx){
//和其他的递归不同，这里不是将递归中叶子节点的元素加入最终集合中，这里时将每个节点的结果都加入到结果集合中
rs.add(new ArrayList<>(path));
//终止条件
if(startIdx >= nums.length){
return;
}
for(int i = startIdx; i < nums.length; i++){
//添加单个元素到子集中
path.add(nums[i]);
//递归
backTracking(nums, i + 1);
//回溯
path.removeLast();
}
}
}