[LeetCode] 40. Combination Sum II

【原题】 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

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

【解释】 和Combination Sum目标相同,但是给定的候选集合中可能会有重复的元素,而再返回的集合当中要求不能重复。且同一个元素不能重复使用。 【思路】 主要的问题在于相同元素会导致结果当中有相同的集合,使用排序可以解决重复集合的问题。

public class Solution {
    public void combinationSumCore(List<List<Integer>> results, List<Integer> result,int[] candidates,int index,int target,int sum){
        if(sum==target) {
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.length;i++){
            if(i>index&&candidates[i]==candidates[i-1])//相同的元素跳过,用来避免同一子集多次加入到结果集合当中
             continue;
            result.add(candidates[i]);
            sum+=candidates[i];
            combinationSumCore(results, result,candidates,i+1,target,sum);//元素不能重复使用所以从下一个元素开始
            sum-=candidates[i];
            result.remove(result.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        List<Integer> result=new ArrayList<>();
        Arrays.sort(candidates);//先排序
        combinationSumCore(results,result,candidates,0,target,0);
        return results;
    }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java进阶之路

java面试热点:集合框架(二)

1840
来自专栏奔跑的蛙牛技术博客

集合(2)

我们知道数组和ArrayList有一个重大缺陷。这个缺陷就从数组的中间位置删除一个元素需要付出重大的代价,因为从数组中间删除一个元素,元素中间的位置都需要向前移...

682
来自专栏菩提树下的杨过

javascript:双链表-插入排序

数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需做这种大量移动,根据每个节点的...

21710
来自专栏赵俊的Java专栏

从源码上分析 LinkedList(附图)

1575
来自专栏WD学习记录

牛客网 从上往下打印二叉树

621
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

711
来自专栏专注研发

JAVA中Sql时间格式与util时间格式转换

  pst.setDate(1, ;//这里的Date是sql中的::得到的是日期

1375
来自专栏云霄雨霁

字符串查找----R向单词查找树

990
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

31012
来自专栏自学笔记

Data Structure堆Tree并查集图论

堆这种数据结构的应用很广泛,比较常用的就是优先队列。普通的队列就是先进先出,后进后出。优先队列就不太一样,出队顺序和入队顺序没有关系,只和这个队列的优先级相关,...

744

扫码关注云+社区