六月伊人,精品人妻一区二区三区四区在线看,chinesexxxxhd老头,99激情网,97精品视频,操你综合网,被躁B 在线观看,欧美午夜一区

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

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

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

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

Each number in candidates may only be used once in the combination.

Note:

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

題意

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

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

說明：

所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。

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

樣例

示例?1:
輸入: candidates =?[10,1,2,7,6,1,5], target =?8,
所求解集為:
[
??[1, 7],
??[1, 2, 5],
??[2, 6],
??[1, 1, 6]
]

示例?2:
輸入: candidates =?[2,5,2,1,2], target =?5,
所求解集為:
[
? [1,2,2],
? [5]
]

題解

回溯算法 + 剪枝

本題解答作者：liweiwei1419
https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/

這道題與上一問的區(qū)別在于：

第 39 題：candidates 中的數(shù)字可以無限制重復(fù)被選??；

第 40 題：candidates 中的每個數(shù)字在每個組合中只能使用一次。

相同點是：相同數(shù)字列表的不同排列視為一個結(jié)果。

如何去掉重復(fù)的集合（重點）

為了使得解集不包含重復(fù)的組合。有以下 2 種方案：

使用哈希表天然的去重功能，但是編碼相對復(fù)雜；
這里我們使用和第 39 題和第 15 題（三數(shù)之和）類似的思路：不重復(fù)就需要按順序搜索，在搜索的過程中檢測分支是否會出現(xiàn)重復(fù)結(jié)果。注意：這里的順序不僅僅指數(shù)組 candidates 有序，還指按照一定順序搜索結(jié)果。

由第 39 題我們知道，數(shù)組 candidates 有序，也是深度優(yōu)先遍歷過程中實現(xiàn)「剪枝」的前提。

將數(shù)組先排序的思路來自于這個問題：去掉一個數(shù)組中重復(fù)的元素。很容易想到的方案是：先對數(shù)組升序排序，重復(fù)的元素一定不是排好序以后相同的連續(xù)數(shù)組區(qū)域的第 1 個元素。也就是說，剪枝發(fā)生在：同一層數(shù)值相同的結(jié)點第 2、3 ... 個結(jié)點，因為數(shù)值相同的第 11 個結(jié)點已經(jīng)搜索出了包含了這個數(shù)值的全部結(jié)果，同一層的其它結(jié)點，候選數(shù)的個數(shù)更少，搜索出的結(jié)果一定不會比第 1個結(jié)點更多，并且是第 1個結(jié)點的子集。（說明：這段文字很拗口，大家可以結(jié)合具體例子，在紙上寫寫畫畫進(jìn)行理解。）

代碼如下：

import?java.util.ArrayDeque;
import?java.util.ArrayList;
import?java.util.Arrays;
import?java.util.Deque;
import?java.util.List;

public?class?Solution?{

????public?List> combinationSum2(int[] candidates, int?target) {
????????int?len = candidates.length;
????????List> res = new?ArrayList<>();
????????if?(len == 0) {
????????????return?res;
????????}

????????// 關(guān)鍵步驟
????????Arrays.sort(candidates);

????????Deque path = new?ArrayDeque<>(len);
????????dfs(candidates, len, 0, target, path, res);
????????return?res;
????}

????/**
?????* @param?candidates 候選數(shù)組
?????* @param?len 冗余變量
?????* @param?begin 從候選數(shù)組的 begin 位置開始搜索
?????* @param?target 表示剩余，這個值一開始等于 target，基于題目中說明的"所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)"這個條件
?????* @param?path 從根結(jié)點到葉子結(jié)點的路徑
?????* @param?res
?????*/
????private?void?dfs(int[] candidates, int?len, int?begin, int?target, Deque path, List> res)?{
????????if?(target == 0) {
????????????res.add(new?ArrayList<>(path));
????????????return;
????????}
????????for?(int?i = begin; i < len; i++) {
????????????// 大剪枝：減去 candidates[i] 小于 0，減去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
????????????if?(target - candidates[i] < 0) {
????????????????break;
????????????}

????????????// 小剪枝：同一層相同數(shù)值的結(jié)點，從第 2 個開始，候選數(shù)更少，結(jié)果一定發(fā)生重復(fù)，因此跳過，用 continue
????????????if?(i > begin && candidates[i] == candidates[i - 1]) {
????????????????continue;
????????????}

????????????path.addLast(candidates[i]);
????????????// 調(diào)試語句 ①
????????????// System.out.println("遞歸之前 => " + path + "，剩余 = " + (target - candidates[i]));

????????????// 因為元素不可以重復(fù)使用，這里遞歸傳遞下去的是 i + 1 而不是 i
????????????dfs(candidates, len, i + 1, target - candidates[i], path, res);

????????????path.removeLast();
????????????// 調(diào)試語句 ②
????????????// System.out.println("遞歸之后 => " + path + "，剩余 = " + (target - candidates[i]));
????????}
????}

????public?static?void?main(String[] args)?{
????????int[] candidates = new?int[]{10, 1, 2, 7, 6, 1, 5};
????????int?target = 8;
????????Solution solution = new?Solution();
????????List> res = solution.combinationSum2(candidates, target);
????????System.out.println("輸出 => "?+ res);
????}
}