成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 40 Combination Sum II

li21 / 624人閱讀

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

題目詳情 
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. 
這道題的意思是，輸入一個(gè)候選數(shù)字集(C)和一個(gè)目標(biāo)數(shù)字(T).要求我們找出C中的不同元素組合，使得這些元素加和等于T。要求C中的每一個(gè)元素在一個(gè)組合中只能被使用一次。


For example, 輸入候選數(shù)字集 [10, 1, 2, 7, 6, 1, 5] 和目標(biāo)數(shù)字 8, 
結(jié)果集應(yīng)當(dāng)是
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
想法

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

因此和39題的解法相比，我們需要進(jìn)行一次對(duì)于重復(fù)元素跳過的操作。

解法 
    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);
            }
        }

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68526.html

相關(guān)文章

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

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...

    leo108 評(píng)論0 收藏0

  • Leetcode 相似題只有題號(hào)不含代碼。

    找出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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Combination Sum I & II

    摘要：和唯一的不同是組合中不能存在重復(fù)的元素，因此，在遞歸時(shí)將初始位即可。 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 評(píng)論0 收藏0

  • [LeetCode] Combination Sum III | Combination Sum I

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

    leiyi 評(píng)論0 收藏0

  • [Leetcode] Combination Sum 組合數(shù)之和

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

    GitCafe 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<