資訊專欄INFORMATION COLUMN
摘要：參考思路和非常類似，只是這里需要增加進(jìn)行重復(fù)處理的部分。題目要求題目中新添的要求包括數(shù)組中存在重復(fù)值，而且數(shù)組中每個(gè)值只可以使用一次。需要注意的是，既然數(shù)組中存在重復(fù)的值，就要注意可能會(huì)將重復(fù)的情況加入結(jié)果數(shù)組。
參考
思路和leetcode39 combination sum 非常類似，只是這里需要增加進(jìn)行重復(fù)處理的部分。請(qǐng)參考我對(duì)leetcode39進(jìn)行解答的這篇博客。
題目要求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] ]
題目中新添的要求包括數(shù)組中存在重復(fù)值，而且數(shù)組中每個(gè)值只可以使用一次。
思路與代碼這題與leetcode39的思路基本相同，利用遞歸的方法記錄前一次情況作為下一次的初始情況。需要注意的是，既然數(shù)組中存在重復(fù)的值，就要注意可能會(huì)將重復(fù)的情況加入結(jié)果數(shù)組。
例如，如果數(shù)組為[2,2,2,6],目標(biāo)值為8，可能會(huì)在結(jié)果數(shù)組中出現(xiàn)多次[2,6]
同樣的，在進(jìn)行遞歸的子遍歷的時(shí)候也要注意，可能會(huì)出現(xiàn)重復(fù)值，例如數(shù)組為[2,2,2,6],目標(biāo)值為10，則結(jié)果集[2,2,6]也可能出現(xiàn)多次，所以在子遍歷中也要記得去除重復(fù)情況。
代碼如下
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);
}
//去除自遍歷中的重復(fù)情況
while(i
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70004.html
摘要：要求中的每一個(gè)元素在一個(gè)組合中只能被使用一次。輸入候選數(shù)字集和目標(biāo)數(shù)字結(jié)果集應(yīng)當(dāng)是想法首先這道題和題非常的相像。因此和題的解法相比，我們需要進(jìn)行一次對(duì)于重復(fù)元素跳過(guò)的操作。 題目詳情 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C...
找出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...
摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要：此時(shí)，若也正好減小為，說(shuō)明當(dāng)前集合是正解，加入數(shù)組。兩個(gè)無(wú)法得到正解的情況是在為，而不為時(shí)，當(dāng)然已經(jīng)無(wú)法得到正解，。在不為而卻已經(jīng)小于等于的情況下，此時(shí)仍要加入其它數(shù)以令為，而要加入的數(shù)都是到的正整數(shù)，所以已無(wú)法滿足令為的條件，。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...
摘要：和唯一的不同是組合中不能存在重復(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...
閱讀 871·2021-10-11 10:59
閱讀 2806·2019-08-30 15:43
閱讀 2136·2019-08-30 11:08
閱讀 1657·2019-08-29 15:20
閱讀 1016·2019-08-29 13:53
閱讀 494·2019-08-26 13:24
閱讀 1644·2019-08-26 13:24
閱讀 2828·2019-08-26 12:08
