<del id="kkcwc"></del>

leetcode40 combination sum 2

Code4App 發布于2019-08-16 10:33 / 1250人閱讀

摘要：參考思路和非常類似，只是這里需要增加進行重復處理的部分。題目要求題目中新添的要求包括數組中存在重復值，而且數組中每個值只可以使用一次。需要注意的是，既然數組中存在重復的值，就要注意可能會將重復的情況加入結果數組。

參考

思路和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

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 2017阿里云服務器40 Leetcod LeetCode Combining

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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