链接
题目:
回溯:子集/组合(元素可重不可复选)
与子集不同的是题目给的元素有重复,如果按之前的做法会导致答案有重复:
有重复元素要先排序!
这里需要添加选择时的条件以修剪节点!
①有重复元素就要先排序 !,让相同的元素靠在⼀起,
②如果发现 nums[i] == nums[i-1] 则跳过 ! 同时 i>start
Java实现:
class Solution {
List<List<Integer>> res=new LinkedList<>();
LinkedList<Integer> path=new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(nums,0);
return res;
}
void dfs(int[] nums,int start){
//每个节点都是子集!
res.add(new LinkedList(path));
for(int i=start;i<nums.length;i++){
//做选择
//修剪,值相同的相邻节点只遍历一次
if(i>start && nums[i]==nums[i-1]){ // i>start !
continue;
}
path.add(nums[i]);
dfs(nums,i+1);
//撤销
path.removeLast();
}
}
}
注意 :i >start !
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/89254.html