【力扣】40. 組合總和 II

Zoom 發(fā)布于2021-11-12 10:36 / 2623人閱讀

摘要：題目給定一個(gè)數(shù)組和一個(gè)目標(biāo)數(shù)，找出中所有可以使數(shù)字和為的組合。中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。注意解集不能包含重復(fù)的組合。示例輸入輸出示例輸入輸出提示答案回溯法排序后去重

題目：
給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

注意：解集不能包含重復(fù)的組合。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:

[	[1,1,6],	[1,2,5],	[1,7],	[2,6]]

示例 2:

輸入: candidates = [2,5,2,1,2], target = 5,
輸出:

[	[1,2,2],	[5]]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

答案：

class Solution {    List<List<Integer>> lists;    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        //回溯法,排序后去重        Arrays.sort(candidates);        lists = new ArrayList<>();        List<Integer> list = new ArrayList<>();        backTrace(list, candidates, target, 0);        return lists;    }    public void backTrace(List<Integer> list, int[] candidates, int target, int index){        if(target == 0){            lists.add(new ArrayList<>(list));            return;        }        if(index >= candidates.length) return;        if(target < 0 && candidates[index] > 0) return;        for(int i = index; i < candidates.length; i++){            list.add(candidates[i]);            backTrace(list, candidates, target - candidates[i], i + 1);            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {                i++;            }            list.remove(list.size() - 1);        }    }}

GPU云服務(wù)器云服務(wù)器力扣 II php計(jì)算總和 python循環(huán)總和

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

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

相關(guān)文章

前端也需要好好的精進(jìn)自己的算法

摘要：算法前端發(fā)展的再快，也不要忘記精進(jìn)自己的算法，算法是靈魂和核心。我會(huì)把我刷過的算法題總結(jié)歸類，不斷完善。算法前端發(fā)展的再快，也不要忘記精進(jìn)自己的算法，算法是靈魂和核心。我會(huì)把我刷過的算法題總結(jié)歸類，不斷完善。歡迎大家關(guān)注。數(shù)組和堆棧數(shù)組去重旋轉(zhuǎn)數(shù)組如何快速找出兩個(gè)數(shù)之和等于某一個(gè)值的兩個(gè)數(shù)？快排排序算法大總結(jié) 快速找到數(shù)組中的最大值多維數(shù)組的展開二分查找有效的括...

hersion 2019-08-23 10:36 評(píng)論0 收藏0
6-9月技術(shù)文章匯總

摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無(wú)狀態(tài)協(xié)議和請(qǐng)求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場(chǎng)景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...

miya 2019-07-30 18:03 評(píng)論0 收藏0
力扣(LeetCode)129

摘要：計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和。說明葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。代碼方法二，自頂向下搜索深度優(yōu)先搜索，搜索過程中維護(hù)一個(gè)當(dāng)前累加值，一旦搜索到葉子節(jié)點(diǎn)，就將現(xiàn)在的當(dāng)前累加值加入結(jié)果中。題目地址：https://leetcode-cn.com/probl...題目描述：給定一個(gè)二叉樹，它的每個(gè)結(jié)點(diǎn)都存放一個(gè) 0-9 的數(shù)字，每條從根到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)字。例如，從...

yzzz 2019-08-16 16:49 評(píng)論0 收藏0
力扣(LeetCode)310

摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。題目地址：https://leetcode-cn.com/probl...題目描述：對(duì)于一個(gè)具有樹特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...

amuqiao 2019-08-16 16:13 評(píng)論0 收藏0
【力扣】47. 全排列 II

摘要：題目給定一個(gè)可包含重復(fù)數(shù)字的序列，按任意順序返回所有不重復(fù)的全排列。示例輸入輸出示例輸入輸出提示答案回溯法使用數(shù)組判斷是否訪問過，排序后跳過與前一個(gè)相同的題目： ...

blastz 2021-11-12 10:36 評(píng)論0 收藏0