摘要:我們需要找出中的數字的不同組合,使得每一種組合的元素加和為。輸入的候選集和目標數字結果集是想法這道題采取了遞歸的思路。每次將一個元素加入的時候,判斷是否滿足中的元素加和等于,如果等于,直接將加入最終返回的結果集。
題目詳情
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.輸入一個不含重復數字的候選的數字集(C)和一個目標數字(T)。我們需要找出c中的數字的不同組合,使得每一種組合的元素加和為T。
For example, 輸入的候選集[2, 3, 6, 7]和目標數字7,
結果集是:
[[7],[2, 2, 3]]
這道題采取了遞歸的思路。
遞歸方法的輸入參數分別是,最終需要返回的結果list,暫存元素list,候選集,離目標元素和的差值,和開始遍歷的起點。
每次將一個元素加入templist的時候,判斷是否滿足templist中的元素加和等于target,如果等于,直接將templist加入最終返回的結果集res。如果加和大于target,那么就沒必要繼續遞歸往templist中增加元素了。如果加和小于list,那么繼續遞歸加入新的元素。
解法public List> combinationSum(int[] nums, int target) { List
> res = new ArrayList
>(); Arrays.sort(nums); backtrack(res,new ArrayList<>(),nums,target,0); return res; } public void backtrack(List
> res,List
temp,int[] nums,int remain,int start){ if(remain <0)return; if(remain == 0)res.add(new ArrayList<>(temp)); else{ for(int i=start;i
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68502.html
摘要:分為每次從里邊循環所有數,已有值減去所有數,新值作為已有值,繼續處理。遇到返回保存,負數去掉 39. Combination SumDescriptionHintsSubmissionsDiscussSolutionGiven a set of candidate numbers (C) (without duplicates) and a target number (T),find...
摘要:在這道題中,我結合了遞歸的思想來。就是將當前的值作為一個潛在的結果值加入一個結果數組將數組作為當前結果傳入下一輪遞歸。 題目要求 Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the ca...
摘要:參考思路和非常類似,只是這里需要增加進行重復處理的部分。題目要求題目中新添的要求包括數組中存在重復值,而且數組中每個值只可以使用一次。需要注意的是,既然數組中存在重復的值,就要注意可能會將重復的情況加入結果數組。 參考 思路和leetcode39 combination sum 非常類似,只是這里需要增加進行重復處理的部分。請參考我對leetcode39進行解答的這篇博客。 題目要求 ...
摘要:輸入輸出分析題目由于我們需要找到多個組合,簡單的使用循環肯定是不行的,這時候我們可以使用回溯算法來解決這個問題。用回溯算法解決問題的一般步驟針對所給問題,定義問題的解空間,它至少包含問題的一個最優解。 題目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...
摘要:要求中的每一個元素在一個組合中只能被使用一次。輸入候選數字集和目標數字結果集應當是想法首先這道題和題非常的相像。因此和題的解法相比,我們需要進行一次對于重復元素跳過的操作。 題目詳情 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C...
閱讀 4270·2021-09-26 10:11
閱讀 2666·2021-07-28 00:37
閱讀 3223·2019-08-29 15:29
閱讀 1178·2019-08-29 15:23
閱讀 3124·2019-08-26 18:37
閱讀 2468·2019-08-26 10:37
閱讀 597·2019-08-23 17:04
閱讀 2347·2019-08-23 13:44