组合总和 II（dfs,leetcode40）-------------------c++实现

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

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

注意：解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

用到的方法还是深搜，但是有一个新的知识点，就是，如果有多个重复点但是搜索的时候需要没有重复组合，则需要一种判断方法：
如果该点和前一个点值相同但是前一个点没有被加入结果队列，则不把该点加入结果队列。
用空间换时间 结果很理想。

注意第一层循环，与前一个值相同则直接跳。

class Solution {
public:
          void dfs(vector& candidates,vector> &result,vector &now,int i,int &target,int &sum)
          {
            
              for(int j=i+1;j
                  if(candidates[j-1]==candidates[j]&&((j-1)!=i))
                           continue;                  //和前一位相同且前一位没入队列,则该数也不如队列.

                  if(sum+candidates[j]>=target)
                  {
                      if(sum+candidates[j]==target)
                        {
                            now.push_back(candidates[j]);
                         result.push_back(now);
                         now.pop_back();
                        }
                        break;
                  }
                  sum+=candidates[j];
                  now.push_back(candidates[j]);
                  dfs(candidates,result,now,j,target,sum);
                  sum-=candidates[j];
                  now.pop_back();
              }
              return;
          }

    vector> combinationSum2(vector& candidates, int target) {
             sort(candidates.begin(),candidates.end());
             vector> result;
             vector now;
             int sum=0;
             for(int i=0;i                                             //选第一个数
                   if(i>0&&candidates[i-1]==candidates[i])
                           continue;
                 if(candidates[i]>=target)
                 { 
                     if(candidates[i]==target)
                           {
                            now.push_back(candidates[i]);
                           result.push_back(now);
                           }
                           break;
                 }
                  sum+=candidates[i];
                  now.push_back(candidates[i]);
                  dfs(candidates,result,now,i,target,sum);
                  sum-=candidates[i];
                  now.pop_back();
             }
             return result;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。