leetcode 40 Combination Sum II

li21 發布于2019-08-15 14:18 / 618人閱讀

摘要：要求中的每一個元素在一個組合中只能被使用一次。輸入候選數字集和目標數字結果集應當是想法首先這道題和題非常的相像。因此和題的解法相比，我們需要進行一次對于重復元素跳過的操作。

題目詳情

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. 這道題的意思是，輸入一個候選數字集(C)和一個目標數字(T).要求我們找出C中的不同元素組合，使得這些元素加和等于T。要求C中的每一個元素在一個組合中只能被使用一次。
For example, 輸入候選數字集 [10, 1, 2, 7, 6, 1, 5] 和目標數字 8, 
結果集應當是
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

想法

首先這道題和39題CombinationSum非常的相像。唯一的差別就在于這道題要求，每一個元素只能被使用一次。

因此和39題的解法相比，我們需要進行一次對于重復元素跳過的操作。

解法

    public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        backtrack(res,new ArrayList(),candidates,target,0);
        return res;
    }
    public void backtrack(List> res,List tempList,int[] candidates,int remain,int start){
        if(remain < 0)return;
        if(remain == 0){
            res.add(new ArrayList<>(tempList));
        }else{
            for(int i=start;i start && candidates[i] == candidates[i-1]) continue;
                tempList.add(candidates[i]);
                backtrack(res,tempList,candidates,remain-candidates[i],i+1);
                tempList.remove(tempList.size()-1);
            }
        }

GPU云服務器云服務器 Combination Leetcod LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68526.html

leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論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
[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
[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
[Leetcode] Combination Sum 組合數之和

摘要：深度優先搜索復雜度時間空間遞歸棧空間思路因為我們可以任意組合任意多個數，看其和是否是目標數，而且還要返回所有可能的組合，所以我們必須遍歷所有可能性才能求解。這題是非常基本且典型的深度優先搜索并返回路徑的題。本質上是有限深度優先搜索。 Combination Sum I Given a set of candidate numbers (C) and a target number (...

GitCafe 2019-08-14 12:31 評論0 收藏0