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

XUI 发布于2021-11-12 10:36 / 769人阅读

摘要：题目给定一个可能有重复数字的整数数组和一个目标数，找出中所有可以使数字和为的组合。中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。示例输入输出示例输入输出提示注意本题与主站题相同答案回溯法排序后去重

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

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

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:

[	[1,1,6],	[1,2,5],	[1,7],	[2,6]]

示例 2:

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

[	[1,2,2],	[5]]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

注意：本题与主站 40 题相同： https://leetcode-cn.com/problems/combination-sum-ii/

答案：

class Solution {    List<List<Integer>> lists;    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        //回溯法,排序后去重        Arrays.sort(candidates);        lists = new ArrayList<>();        List<Integer> list = new ArrayList<>();        backTrace(list, candidates, target, 0);        return lists;    }    public void backTrace(List<Integer> list, int[] candidates, int target, int index){        if(target == 0){            lists.add(new ArrayList<>(list));            return;        }        if(index >= candidates.length) return;        if(target < 0 && candidates[index] > 0) return;        for(int i = index; i < candidates.length; i++){            list.add(candidates[i]);            backTrace(list, candidates, target - candidates[i], i + 1);            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {                i++;            }            list.remove(list.size() - 1);        }    }}

超融合服务器私有云 js组合重复数据元素集合拖动Html元素集合 java集合判断元素

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123185.html

k个一组翻转链表哔哩哔哩2020校园招聘笔试题/LeetCode_25（困难）讲解

摘要：三代码实现用空格分割链表每个元素将链表分为组组组内翻转，如果不够一组，就不进行翻转。下一组的起始位置为什么的上限是输入的要求是每个元素后面跟个但是最后一个没有，最后一个元素就要最后输出。 ...

CntChen 2021-09-10 10:50 评论0 收藏0
复数乘法哔哩哔哩2020校园招聘面试题详解

摘要：二解题方法分别获取两个字符串的整数部分，再把这两部分字符串转换成整数，最后用复数乘法公式得出结果。复数乘法公式也就是说我们只需要在两个字符串中获取这四个数字。一...

ThreeWords 2021-09-08 09:36 评论0 收藏0
【算法】剑指 Offer II 110. 所有路径｜797. 所有可能的路径（多语言实现）

摘要：遍历路径，找到所有可以到达终点节点的路径就是结果。提示中说保证输入为有向无环图，所以我们可以认为节点间一定有着某种排列的顺序，从头到尾怎样可以有最多的路径呢，那就是在保证没有环路的情况下，所有节点都尽可能多的连接着其他节点。 ...

wangdai 2021-11-23 09:51 评论0 收藏0
带你新学期领跑！8000字吐血总结数据结构之单链表

摘要：实际中更多是作为其他数据结构的子结构，如哈希桶图的邻接表等等。单链表的结构头节点数据节点三单链表的实现光说不练假把式，我们了解了链表的结构用处。对于无头单向链表。 ...

abson 2021-09-07 09:59 评论0 收藏0
【Leetcode】二叉树专题(仅需【7道题】就可以带你入门二叉树基本玩法)

摘要：文章目录一剑指二叉树的镜像剑指二叉树的镜像思路递归二剑指对称的二叉树剑指对称的二叉树思路递归三剑指二叉树的深度剑指二叉树的深度思路递归四剑指平衡二叉树剑指平衡二叉树思路递归五相同的 ...

lindroid 2021-11-18 10:02 评论0 收藏0