摘要:題目要求輸入和,找到所有個(gè)不同數(shù)字的組合,這些組合中數(shù)字的和為參考,解答這是一道典型的的題目,通過(guò)遞歸的方式記錄嘗試的節(jié)點(diǎn),如果成功則加入結(jié)果集,如果失敗則返回上一個(gè)嘗試的節(jié)點(diǎn)進(jìn)行下一種嘗試。
題目要求
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]
輸入k和n,找到所有k個(gè)不同數(shù)字的組合,這些組合中數(shù)字的和為n
參考Combination Sum I ,Combination Sum II
解答這是一道典型的backtracking的題目,通過(guò)遞歸的方式記錄嘗試的節(jié)點(diǎn),如果成功則加入結(jié)果集,如果失敗則返回上一個(gè)嘗試的節(jié)點(diǎn)進(jìn)行下一種嘗試。
public List> combinationSum3(int k, int n) { List
> result = new ArrayList
>(); combinationSum3(k,n,1,result, new ArrayList
()); return result; } public void combinationSum3(int k, int n, int startNumber, List > result, List
current){ if(k==0 && n==0){ result.add(new ArrayList (current)); return;} if(k==0 || n<0) return; for(int i = startNumber ; i<=9 ; i++){ if(i>n){ break; } current.add(i); combinationSum3(k-1, n-i, i+1, result, current); current.remove(current.size()-1); } }
想要了解更多開(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://m.specialneedsforspecialkids.com/yun/67448.html
找出string里的單詞。 186. Reverse Words in a String II, 434. Number of Segments in a String combination類(lèi)型題 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...
摘要:此時(shí),若也正好減小為,說(shuō)明當(dāng)前集合是正解,加入數(shù)組。兩個(gè)無(wú)法得到正解的情況是在為,而不為時(shí),當(dāng)然已經(jīng)無(wú)法得到正解,。在不為而卻已經(jīng)小于等于的情況下,此時(shí)仍要加入其它數(shù)以令為,而要加入的數(shù)都是到的正整數(shù),所以已無(wú)法滿(mǎn)足令為的條件,。 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...
摘要:深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸棧空間思路因?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 (...
摘要:參考思路和非常類(lèi)似,只是這里需要增加進(jìn)行重復(fù)處理的部分。題目要求題目中新添的要求包括數(shù)組中存在重復(fù)值,而且數(shù)組中每個(gè)值只可以使用一次。需要注意的是,既然數(shù)組中存在重復(fù)的值,就要注意可能會(huì)將重復(fù)的情況加入結(jié)果數(shù)組。 參考 思路和leetcode39 combination sum 非常類(lèi)似,只是這里需要增加進(jìn)行重復(fù)處理的部分。請(qǐng)參考我對(duì)leetcode39進(jìn)行解答的這篇博客。 題目要求 ...
閱讀 899·2021-10-25 09:44
閱讀 1272·2021-09-23 11:56
閱讀 1194·2021-09-10 10:50
閱讀 3140·2019-08-30 15:53
閱讀 2143·2019-08-30 13:17
閱讀 624·2019-08-29 18:43
閱讀 2501·2019-08-29 12:57
閱讀 862·2019-08-26 12:20