组合总和||

1.给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& num,int sum,int target,int startIndex,vector<bool>& used)
{
    if(sum>target)
    return ;
    if(sum==target)
    {
        result.push_back(path);
        return ;
    }
    for(int i=startIndex;i<num.size()&&sum+num[i]<=target;i++)
    {
        if(i>0&&num[i]==num[i-1]&&used[i-1]==false)
        continue;
        sum+=num[i];
        path.push_back(num[i]);
        used[i]=true;
        backtracking(num,sum,target,i+1,used);
        used[i]=false;
        sum-=num[i];
        path.pop_back();
    }
    
 } 
 vector<vector<int>> combine(vector<int>& num,int target)
 {
     vector<bool> used(num.size(),false);
     path.clear();
     result.clear();
     sort(num.begin(),num.end());
     backtracking(num,0,target,0,used);
     return result;
 }
 int main()
 {
     vector<int> num={1,1,2};
     vector<vector<int>> t=combine(num,2);
     for(const auto& n:t)
     {
         for(int m:n)
         {
            cout<<m<<" ";
         }
         cout<<endl;
     }
  return 0;    
 }
 

思路：本题主要的难点是去重，我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重，树层去重的话，需要对数组排序。这个集合去重的重任是用used来完成的。

终止条件为 sum > target 和 sum == target，如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过

used[i - 1] == false，说明同一树层candidates[i - 1]使用过

可能有的人想，为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上。

注意：sum + candidates[i] <= target为剪枝操作。