[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 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 移动零题目分析

给一个数组 nums 写一个函数将0 移动到数组的最后面,非零元素保持原数组的顺序

672
来自专栏用户画像

4.2.2 常见的数据寻址方式

如单地址的指令格式,就不是明显地在地址字段中指出第二操作数的地址,而是规定累加器ACC作为第二操作数,指令格式明显指出的仅是第一操作数的地址。因此,累加器ACC...

622
来自专栏柠檬先生

你不知道的javaScript笔记(4)

类型: JavaScript 有7种内置类型 空值 (null) 未定义(undefined) 布尔值(boolean) 数字(number) 字符串(stri...

2085
来自专栏老司机的技术博客

宝宝都能学会的python编程教程6:列表(list)

上期编程题的答案如上图。 列表(list) list是一种有序的集合,可以随时添加和删除其中的元素。 当索引超出了范围时,Python会报一个IndexErr...

3386
来自专栏Golang语言社区

Golang语言社区--Go语言基础第四节类型

大家好,我是Golang语言社区主编彬哥,这节给大家讲解Go语言中的类型。

4365
来自专栏LeetCode

LeetCode 662. Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree...

1010
来自专栏Python中文社区

Python生成器的使用技巧详解

之前我们介绍了列表解析式,他的优点很多,比如运行速度快、编写简单,但是有一点我们不要忘了,他是一次性生成整个列表。如果整个列表非常大,这对内存也同样会造成很大压...

1043
来自专栏快乐八哥

JavaScript循环读书笔记

循环知识:自我重复的风险 第一部分: 重复运行的代码就可以使用循环来解决。JavaScript的重复机制为循环(loop) for:适合重复动作已知次数的循环。...

1777
来自专栏冰霜之地

深入解析 Go 中 Slice 底层实现

切片是 Go 中的一种基本的数据结构,使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来,为了开发者可以更加方便的使一个数据结构可以自动增加和...

1013
来自专栏苦逼的码农

一些常用的算法技巧总结

数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

643

扫码关注云+社区