LeetCode 90:子集 II

导读:本篇文章讲解 LeetCode 90:子集 II,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

链接
题目:
在这里插入图片描述

回溯:子集/组合(元素可重不可复选)

子集不同的是题目给的元素有重复,如果按之前的做法会导致答案有重复:
有重复元素要先排序!

在这里插入图片描述

在这里插入图片描述

这里需要添加选择时的条件以修剪节点!
①有重复元素就要先排序 !,让相同的元素靠在⼀起,
②如果发现 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

(0)
小半的头像小半

相关推荐

极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!