首页 > 其他分享 >剑指Offer 082. 含有重复元素集合的组合

剑指Offer 082. 含有重复元素集合的组合

时间:2023-01-14 23:56:28浏览次数:47  
标签:target Offer int 082 nums len track candidates 集合

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次,解集不能包含重复的组合。

输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]


输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

这一题总体思路与组合类似 但是更与不重复子集相似 相当于再加上一个条件 在本题中 target就是这个条件

    List<List<Integer>> res = new LinkedList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int candi_len = candidates.length;
        Arrays.sort(candidates);
        LinkedList<Integer> subset = new LinkedList<>();
        backtrack(candidates, 0, candi_len, target, subset);
        return res;
    }

    public void backtrack(int[] nums, int start, int len, int target, LinkedList<Integer> track){
        if (target == 0) {
            res.add(new ArrayList<>(track));
            return;
        }
        for(int i = start; i < len; i++){
          //剪枝 将target值减去 并且带入到下次回溯中 因为之前已经给数组排序过了 如果大于了 就说明超过了 就不用再进行回溯了
            if(nums[i] > target){
                break;
            }
            if(i != start && nums[i] == nums[i-1]){
                continue;
            }
            track.addLast(nums[i]);
            backtrack(nums, i+1, len, target - nums[i], track);
            track.removeLast();
        }
    }
}

标签:target,Offer,int,082,nums,len,track,candidates,集合
From: https://www.cnblogs.com/rickierun/p/17052848.html

相关文章

  • Python之集合操作举例
    #集合的操作(Set、frozenset)#集合特点:无序、元素不可重复、执行效率高但是比列表占用空间大,空间换时间s={"a","b","c"}s=set("abcd")print(s)#{'d','b',......
  • Java集合之LinkedList源码分析
    LinkedList文章目录​​LinkedList​​​​LinkedList介绍​​​​LinkedList的方法总结​​​​LinkedList源码分析​​​​GetElement​​​​RemoveElement​​​​......
  • list.remove()时出问题,集合的remove方法注意事项2
    不要在foreach循环里进行元素的remove/add操作。remove元素请使用Iterator方式,如果并发操作,需要对Iterator对象加锁。另可参考:​list.remove()时出问题,集合的re......
  • Java集合 - ConcurrentHashMap
    介绍ConcurrentHashMap技术是为了解决问题而生的,ConcurrentHashMap解决了多个线程同时操作一个HashMap时,可能出现的内部问题。当多个线程同时操作一个HashMap时,有可......
  • Java集合 - ConcurrentHashMap
    介绍ConcurrentHashMap技术是为了解决问题而生的,ConcurrentHashMap解决了多个线程同时操作一个HashMap时,可能出现的内部问题。当多个线程同时操作一个HashMap时,有可......
  • 运用List集合实现学生管理系统
    packagecom.集合进阶;importjava.util.*;publicclass杨杨牌学生储存系统{publicstaticvoidmain(String[]args){List<学生类>c=newArrayList<学生......
  • (五)Java集合
    Java集合1、Java集合(容器)Java容器分为Collection和Map两大类,各自都有很多子类。Collections是一个包装类,包含有关集合的各种静态方法,不能被实例化,Collections集合......
  • Python字典和集合初窥
    (Python进阶10-字典与集合)1字典字典和列表类似,同样是可变序列,不过与列表不同,字典是无序的。字典的主要特征:1.1字典的创建和删除字典的每个元素都包含“键”和“......
  • List集合
    List集合的常用方法voidadd(intindexEelement):在此集合中的指定位置插入指定的元素Eremove(intindex):删除指定索引处的元素,返回被删除的元素Eset(in......
  • Collection集合
    Collection集合常用方法:booleanadd(Ee):添加元素booleanremove(objecto):从集合中移除指定的元素voidclear():清空集合中的元素booleancontains(objecto):判断集合......