40.组合总和II

题目
给定一个数组 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]
]

思路
沿用39题的代码，backTrack(candidates, i + 1, target - candidates[i], item, result);改为i+1，即当前数不可重复使用，利用flag = find(result.begin(), result.end(), if(flag == result.end())item);判断是否有重复项

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> candidates = { 10, 1, 2, 7, 6, 1, 5 };
    int target = 8;
    void backTrack(std::vector<int>& candidates, int start, int target, vector<int> item, vector<vector<int>>& result)
    {
        if (target < 0)
        {
            return;
        }
        if (target == 0)
        {
            vector<vector<int>>::iterator flag;
             flag = find(result.begin(), result.end(), item);
            if(flag == result.end())
            {
                result.push_back(item);
                return;
            }

        }
        for (int i = start; i < candidates.size(); i++)
        {
            item.push_back(candidates[i]);
            backTrack(candidates, i + 1, target - candidates[i], item, result);
            item.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> item;
        int i = 0;
        backTrack(candidates, 0, target, item, result);
        sort(result.begin(), result.end());
        return result ;
    }
};

int main(int argc, char* argv[])
{
    Solution sol;
    auto test = sol.candidates;
    auto tar = sol.target;
    auto res = sol.combinationSum2(test, tar);
    return 0;
}