專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友在網(wǎng)上發(fā)文為什么華為到處招人，打開招聘網(wǎng)站全是華為的。我覺得主要是華為人多，20.7萬人，就算每年更替5%-10%就是1-2萬人。招的人很多都是大學(xué)生，華為又看重學(xué)校，這些新人集中到少數(shù)名校，那就顯得尤為突出了。

還有就是華為業(yè)務(wù)發(fā)展迅速，項目需求增長，需要更多的技術(shù)支持。同時，華為對人才的要求也比較高，既要人多又要能力強，這就造成了用人部門招聘需求強烈，而合適的人才相對較少，所以HR們會積極尋找符合要求的人才，因此得不斷招聘來滿足需求，給人一種天天在招人的感覺。還一種可能是外包為了拿提成，不斷的約人。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第40題：組合總和 II。

問題描述

來源：LeetCode第40題

難度：中等

給定一個候選人編號的集合 candidates 和一個目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的每個數(shù)字在每個組合中只能使用一次 。

注意：解集不能包含重復(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

問題分析

昨天我們剛講過和這題類似的一道題 ，不過昨天那道題數(shù)組中是沒有重復(fù)數(shù)字的，而今天這題數(shù)組中可能會 有 重復(fù)數(shù)字 ，如果有重復(fù)數(shù)字就會出現(xiàn)重復(fù)的組合，所以解這題的關(guān)鍵點是怎么過濾掉重復(fù)的組合， 我們畫個圖看下：

選擇的過程可以把它看作是一棵樹，因為每個數(shù)字最多只能選擇一次，所以選擇完當(dāng)前數(shù)字之后下一步要從它的下一個數(shù)字開始。上面圖中因為有相同的數(shù)字，所以結(jié)果出現(xiàn)了重復(fù)。只需要把重復(fù)的剪掉即可。

在計算之前我們需要先對數(shù)組排序，這樣重復(fù)的數(shù)字就會挨著了，當(dāng)出現(xiàn)重復(fù)數(shù)字的時候，前面數(shù)字構(gòu)成的子集實際上是包含后面數(shù)字構(gòu)成的所有子集，所以當(dāng)出現(xiàn)重復(fù)數(shù)字的時候我們需要把后面數(shù)字構(gòu)成的分支剪掉即可。

JAVA：

public List
         
         
 > combinationSum2( int[] candidates,  int target) {     List > ans =  new ArrayList<>();     Arrays.sort(candidates); // 先排序     dfs(ans,  new ArrayList<>(), candidates, target,  0);      return ans; } private void dfs(List > ans, List  path,                   int[] candidates,  int target,  int start)  {      if (target ==  0) {         ans.add( new ArrayList<>(path));          return;     }      for ( int i = start; i < candidates.length; i++) {          // 因為是有序的，后面的值越來越大，直接終止。          if (target < candidates[i])              break;          if (i > start && candidates[i] == candidates[i -  1])              continue;  // 去掉重復(fù)的，后面分支就不要選擇了         path.add(candidates[i]); // 選擇         dfs(ans, path, candidates, target - candidates[i], i +  1);         path.remove(path.size() -  1); // 撤銷選擇     } }

C++：

public:     vector

 > combinationSum2(vector

  &candidates, int target) {         vector

 > ans;         vector

  path;         sort(candidates.begin(), candidates.end());// 先排序         dfs(ans, path, candidates, target, 0);         return ans;     }     void dfs(vector

 > &ans, vector

  &path,              vector

  &candidates, int target, int start) {         if (target == 0) {             ans.emplace_back(path);             return;         }         for (int i = start; i < candidates.size(); i++) {             // 因為是有序的，后面的值越來越大，直接終止。             if (target < candidates[i])                 break;             if (i > start && candidates[i] == candidates[i - 1])                 continue; // 去掉重復(fù)的，后面分支就不要選擇了             path.emplace_back(candidates[i]);// 選擇             dfs(ans, path, candidates, target - candidates[i], i + 1);             path.pop_back();// 撤銷選擇         }     }

C：

int cmp(const void *a, const void *b) {     return *(const int *) a - *(const int *) b; } void dfs(int **ans, int *path, int *candidates, int candidatesSize, int target,          int start, int *returnSize, int **returnColumnSizes, int pathCount) {     if (target == 0) {         ans[*returnSize] = (int *) malloc(pathCount * sizeof(int));         memcpy(ans[*returnSize], path, pathCount * sizeof(int));         (*returnColumnSizes)[*returnSize] = pathCount;         (*returnSize)++;         return;     }     for (int i = start; i < candidatesSize; i++) {         // 因為是有序的，后面的值越來越大，直接終止。         if (target < candidates[i])             break;         if (i > start && candidates[i] == candidates[i - 1])             continue; // 去掉重復(fù)的，后面分支就不要選擇了         path[pathCount++] = candidates[i];// 選擇         dfs(ans, path, candidates, candidatesSize, target - candidates[i],             i + 1, returnSize, returnColumnSizes, pathCount);         --pathCount;// 撤銷選擇     } } int **combinationSum2(int *candidates, int candidatesSize, int target,                       int *returnSize, int **returnColumnSizes) {     // 先進(jìn)行排序     qsort(candidates, candidatesSize, sizeof(int), cmp);     int n = 3000;     *returnSize = 0;     int **ans = malloc(n * sizeof(int *));     *returnColumnSizes = malloc(n * sizeof(int));     int *path = malloc(n * sizeof(int));     dfs(ans, path, candidates, candidatesSize, target, 0, returnSize, returnColumnSizes, 0);     return ans; }

Python：

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:     def backtrack(num: int, start: int):         if num == 0:             ans.append(path[:])             return         for i in range(start, len(candidates)):             # 因為是有序的，后面的值越來越大，直接終止。             if num < candidates[i]:                 break             if i > start and candidates[i] == candidates[i - 1]:                 continue  # 去掉重復(fù)的，后面分支就不要選擇了             path.append(candidates[i])  # 選擇             backtrack(num - candidates[i], i + 1)             path.pop()  # 撤銷選擇     candidates.sort()  # 先對數(shù)組進(jìn)行排序     ans = []  # 需要返回的結(jié)果     path = []     backtrack(target, 0)     return ans

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。