leetcode40 combination sum 2

Code4App 发布于2019-08-16 10:33 / 996人阅读

摘要：参考思路和非常类似，只是这里需要增加进行重复处理的部分。题目要求题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。

参考

思路和leetcode39 combination sum 非常类似，只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。

题目要求

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]
]

题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。

思路与代码

这题与leetcode39的思路基本相同，利用递归的方法记录前一次情况作为下一次的初始情况。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。
例如，如果数组为[2,2,2,6],目标值为8，可能会在结果数组中出现多次[2,6]
同样的，在进行递归的子遍历的时候也要注意，可能会出现重复值，例如数组为[2,2,2,6],目标值为10，则结果集[2,2,6]也可能出现多次，所以在子遍历中也要记得去除重复情况。
代码如下

public class CombinationSum2_40 {
    List> result = new ArrayList>();
    public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int length = candidates.length;
        for(int i = 0 ; i0 && candidates[i] == candidates[i-1]){continue;}
            if(candidates[i] == target){
                result.add(Arrays.asList(candidates[i]));
            }else{
                List temp = new ArrayList();
                temp.add(candidates[i]);
                combinationSum2(candidates, target-candidates[i], i+1, temp);
            }
        }
        return result;
    }
    
    public void combinationSum2(int[] candidates, int target, int startAt, List currentList){
        for(int i = startAt ; i target){
                return;
            }
            if(candidates[i] < target){
                List temp = new ArrayList(currentList);
                temp.add(candidates[i]);
                combinationSum2(candidates, target-candidates[i], i+1, temp);
            }
            //去除自遍历中的重复情况
            while(i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

idc机房托管超融合服务器 2017阿里云服务器40 Leetcod LeetCode Combining

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

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

leetcode 40 Combination Sum II

摘要：要求中的每一个元素在一个组合中只能被使用一次。输入候选数字集和目标数字结果集应当是想法首先这道题和题非常的相像。因此和题的解法相比，我们需要进行一次对于重复元素跳过的操作。题目详情 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C...

li21 2019-08-15 14:18 评论0 收藏0
Leetcode 相似题只有题号不含代码。

找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] Combination Sum III | Combination Sum I

摘要：此时，若也正好减小为，说明当前集合是正解，加入数组。两个无法得到正解的情况是在为，而不为时，当然已经无法得到正解，。在不为而却已经小于等于的情况下，此时仍要加入其它数以令为，而要加入的数都是到的正整数，所以已无法满足令为的条件，。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...

leiyi 2019-08-14 15:48 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0