体内射精视频,日韩AV一卡二卡,成人AV天天干,成人伊人影视在线,插逼视频网站,逼片网站,亚洲欧美精品一区,亚洲无码专区区免费

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?組合總和，我們先來看題面：

https://leetcode-cn.com/problems/combination-sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

題意

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

candidates 中的數(shù)字可以無限制重復(fù)被選取。

說明：

所有數(shù)字（包括 target）都是正整數(shù)。

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

樣例

示例?1：

輸入：candidates = [2,3,6,7], target = 7,
所求解集為：
[
??[7],
??[2,2,3]
]

示例?2：

輸入：candidates = [2,3,5], target = 8,
所求解集為：
[
? [2,2,2,2],
? [2,3,3],
? [3,5]
]

題解

回溯法

回溯算法關(guān)鍵在于:不合適就退回上一步，然后通過約束條件, 減少時(shí)間復(fù)雜度.

假設(shè)candidates = [2, 3, 6, 7]，target = 7
以 target = 7 為根結(jié)點(diǎn)，每一個(gè)分支做減法。減到 0 或者負(fù)數(shù)的時(shí)候，剪枝。其中，減到 0 的時(shí)候結(jié)算，這里 “結(jié)算” 的意思是添加到結(jié)果集。

代碼如下：

class?Solution?{
????public?List> combinationSum(int[] candidates, int?target) {
????????List> res = new?ArrayList<>();
????????Arrays.sort(candidates);
????????backtrack(candidates, target, res, 0, new?ArrayList());
????????return?res;
????}
????private?void?backtrack(int[] candidates, int?target, List> res,
????????int?i, ArrayList tmp_list) {
????????if?(target < 0) return;
????????if?(target == 0) {
????????????res.add(new?ArrayList<>(tmp_list)); return;
????????}
????????for?(int?start = i; start < candidates.length; start++) {
????????????if?(target < candidates[start]) break;
????????????tmp_list.add(candidates[start]);
????????????backtrack(candidates, target - candidates[start], res, start, tmp_list);
????????????tmp_list.remove(tmp_list.size() - 1);
????????}
????}
}