#LeetCode:40. Combination Sum II

先排序數值,然後用 Backtracking 去找尋所有可能性,在過程中如果決定不選某個數字,則要跳過全部跟該數值等值的部分,而這也是為什麼要先排序的原因,排序後的數列會比較好做跳過整段相同數字的這件事情。

C++(8ms)

/*******************************************************/
/* LeetCode 40. Combination Sum II                     */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/04                                 */
/*******************************************************/
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
  void getCombinationSum(vector<vector<int>> &currentAnswers, vector<int> &currentUsed, vector<int>& candidates, int startIndex, int target){
    if(target == 0){
      currentAnswers.push_back(currentUsed);
      return;
    }

    for(int i = startIndex ; i < candidates.size() ; ++i){
      if(target < candidates[i]) break;

      currentUsed.push_back(candidates[i]);
      getCombinationSum(currentAnswers, currentUsed, candidates, i + 1, target - candidates[i]);
      currentUsed.pop_back();

      while(i < candidates.size() - 1 && candidates[i] == candidates[i+1]) ++i;
    }
  }

  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> answers;
    vector<int> currentUsed;
    sort(candidates.begin(), candidates.end());
    getCombinationSum(answers, currentUsed, candidates, 0, target);
    return answers;
  }
};

1 回應

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: