摘要:在這道題中,我結(jié)合了遞歸的思想來(lái)。就是將當(dāng)前的值作為一個(gè)潛在的結(jié)果值加入一個(gè)結(jié)果數(shù)組將數(shù)組作為當(dāng)前結(jié)果傳入下一輪遞歸。
題目要求
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]
一個(gè)整數(shù)數(shù)組,數(shù)組中的值不重復(fù),要求在數(shù)組中找到所有的子數(shù)組,子數(shù)組滿足元素的和為目標(biāo)值的條件
思路和代碼這道題目有一個(gè)標(biāo)簽是backtracking,即在前一種條件的情況下計(jì)算當(dāng)前條件產(chǎn)生的結(jié)果值。在這道題中,我結(jié)合了遞歸的思想來(lái)。就是將當(dāng)前的值作為一個(gè)潛在的結(jié)果值加入一個(gè)結(jié)果數(shù)組將數(shù)組作為當(dāng)前結(jié)果傳入下一輪遞歸。
public class CombinationSum_39 { List> result = new ArrayList
>(); public List
> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); for(int i = 0 ; i
temp = new ArrayList (); temp.add(candidates[i]); combinationSum(candidates, i, target-candidates[i], temp); } } return result; } public void combinationSum(int[] candidates, int start, int target, List currentResult){ for(int i = start ; i < candidates.length ; i++){ if(candidates[i] == target){ currentResult.add(candidates[i]); result.add(currentResult); return; } if(candidates[i] > target){ return; } if(candidates[i] < target){ List temp = new ArrayList (); temp.addAll(currentResult); temp.add(candidates[i]); combinationSum(candidates, i, target-candidates[i], temp); } } } }
想要了解更多開發(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://specialneedsforspecialkids.com/yun/70006.html
摘要:分為每次從里邊循環(huán)所有數(shù),已有值減去所有數(shù),新值作為已有值,繼續(xù)處理。遇到返回保存,負(fù)數(shù)去掉 39. Combination SumDescriptionHintsSubmissionsDiscussSolutionGiven a set of candidate numbers (C) (without duplicates) and a target number (T),find...
摘要:參考思路和非常類似,只是這里需要增加進(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)行解答的這篇博客。 題目要求 ...
摘要:輸入輸出分析題目由于我們需要找到多個(gè)組合,簡(jiǎn)單的使用循環(huán)肯定是不行的,這時(shí)候我們可以使用回溯算法來(lái)解決這個(gè)問(wèn)題。用回溯算法解決問(wèn)題的一般步驟針對(duì)所給問(wèn)題,定義問(wèn)題的解空間,它至少包含問(wèn)題的一個(gè)最優(yōu)解。 題目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...
摘要:要求中的每一個(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...
閱讀 2574·2021-10-08 10:04
閱讀 2735·2021-09-06 15:02
閱讀 792·2019-08-30 13:50
閱讀 1547·2019-08-30 13:21
閱讀 2586·2019-08-30 11:15
閱讀 2113·2019-08-29 17:19
閱讀 1574·2019-08-26 13:55
閱讀 1261·2019-08-26 10:15