题解 | 加起来和为目标值的组合

解法一：回溯

思路步骤：

涉及到搜索所有可能的组合类型时，一般情况下都会想到用回溯法。题目中结果集不能重复，这是一个应该注意的点。

• 开两个数组rseult，path存储结果与可能的路径集。

• 处理递归终止情况：sum+=num[i]>target时，终止循环（sum为组合数和）

• 利用一个num.size()大小的数组used进行去重。

• 参考图解：
  

C++参考代码：

class Solution {
private:
        //回溯函数
    vector<vector<int>> result;//原来存储最终结果的数组
    vector<int> path;//存储符合条件的路径集
    void backtracking(vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){
        if(sum==target){
            result.push_back(path);
            return;
        }
       //循环+剪枝   ：去重的具体代码：used[i-1]==false
        //剪枝的具体代码：sum+candidates[i]<=target;
       for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;i++){
           if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false){
               continue;
           }
           //累加求和
           sum+=candidates[i];
           path.push_back(candidates[i]);
            //更新used数组状态
           used[i]=true;
            //回溯(递归)函数调用
           backtracking(candidates, target,sum,i+1,used);
           used[i]  =false;
           sum-=candidates[i];//回溯
           path.pop_back();//回溯
       }
    }
public:
    vector<vector<int>> combinationSum2(vector<int> &num, int target) {
        vector<bool> used(num.size(), false);
        //STL中vector的排序函数