leetcode 40 Combination Sum II

li21 發(fā)布于2019-08-15 14:18 / 671人閱讀

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

題目詳情

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

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

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

leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序寫現(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序寫～現(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理 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

摘要：此時，若也正好減小為，說明當前集合是正解，加入數(shù)組。兩個無法得到正解的情況是在為，而不為時，當然已經(jīng)無法得到正解，。在不為而卻已經(jīng)小于等于的情況下，此時仍要加入其它數(shù)以令為，而要加入的數(shù)都是到的正整數(shù)，所以已無法滿足令為的條件，。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...

leiyi 2019-08-14 15:48 評論0 收藏0
[Leetcode] Combination Sum 組合數(shù)之和

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

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