【LeetCode】40 組合總和 II (C++)

原題位址：https://leetcode-cn.com/problems/combination-sum-ii/submissions/

題目描述：

給定一個數組 candidates 和一個目标數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中隻能使用一次。

說明：

    所有數字（包括目标數）都是正整數。

    解集不能包含重複的組合。

示例 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]

]

解題方案：

這道題兩個月之前沒有做出來，最近做了幾道回溯的題然後就有了一些思路。有一個自己做的時候沒有解決的問題就是去重，沒有想到好的方法，然後去網上搜了一下，解決方法就是在第一層裡連續幾個相同的數隻周遊第一個數。還發現網上的解法是把target每次減掉一個數，不是像我那樣每次都周遊作和。雖然時間複雜度沒有提升，但是覺得那種做法更巧妙一些，也省去了不必要的計算。

代碼：

class Solution {
public:
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> temp;
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        getans(candidates, target, 0, result, temp);
        return result;
    }
    void getans(vector<int> candidates, int target, int start, vector<vector<int>> &result, vector<int> temp)
    {
        if(target == 0)
        {
            result.push_back(temp);
        }        
        else if(target > 0)
        {  
            int k = candidates.size() - 1;
            while(target < candidates[k])
                k --;
            for(int i = start; i <= k; i ++)
            {
                if(i != start && candidates[i] == candidates[i - 1])
                    continue;
                temp.push_back(candidates[i]);
                getans(candidates, target - candidates[i], i + 1, result, temp);
                temp.pop_back();
            }
        }
    }
};