【Combination Sum II 】cpp-白红宇

【Combination Sum II 】cpp

阅读量：6194 次

发布时间：2019-06-21

本文共 3177 字，大约阅读时间需要 10 分钟。

题目：

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.

Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,

A solution set is:

[1, 7]

[1, 2, 5]

[2, 6]

[1, 1, 6]

代码：

class Solution {public:        vector
     
      
        > combinationSum2(vector
       
        & candidates, int target)        {            vector
        
         
           > ret;            std::sort(candidates.begin(), candidates.end());            int sum = 0;            vector
          
            tmp; Solution::dfs(ret, tmp, sum, candidates, 0, candidates.size()-1, target); return ret; } static void dfs( vector
           
            
              >& ret, vector
             
              & tmp, int &sum, vector
              
               & candidates, int begin, int end, int target ) { if ( sum>target ) return; if ( sum==target ) { ret.push_back(tmp); return; } int pre = candidates[0]-1; for ( int i=begin; i<=end; ++i ) { if ( pre==candidates[i] ) continue; pre = candidates[i]; if ( sum+candidates[i]<=target ) { sum += candidates[i]; tmp.push_back(candidates[i]); Solution::dfs(ret, tmp, sum, candidates, i+1, end, target); tmp.pop_back(); sum -= candidates[i]; } } }};

tips：

此题与不同之处在于，每个元素只能取一次，并且解集中不能有重复的。

用深搜模板：

1. 如果元素都没有重复的，就是最直接的深搜模板（注意dfs到下一层的时候，传入的begin是i+1而不是i了）

2. 如果元素有重复的，再处理时就跳过前面出现过的元素（前提是candidates都排好序）；这里有个技巧就是维护一个pre变量，并且初始化pre为candidates[0]-1，即比candidates元素都小，这样不用改变循环的结构就可以直接处理

3. 还有一个疑问，为什么不用判断begin>end的情况？比如，{1，1，1} ，4 这种输入，显然所有元素加一起也满足不了结果。进行到最后一定会出现begin==3 end==2的情况。这种情况也不要紧，因为begin大于end就不处理了，直接返回了，所以也没事。

===========================================

第二次过这道题，遇到这种不要重复结果的，有些规律：就是在每一层dfs的时候，如果candidate[i]出现连续两个重复，就跳过后面的那个。

class Solution {public:        vector
     
      
        > combinationSum2(            vector
       
        & candidates, int target)        {            sort(candidates.begin(), candidates.end());            vector
        
         
           > ret;            vector
          
            tmp; Solution::dfs(ret, tmp, candidates, 0, candidates.size()-1, target); return ret; } static void dfs( vector
           
            
              >& ret, vector
             
              & tmp, vector
              
               & candidates, int begin, int end, int target ) { if ( target<0 ) return; if ( target==0 ) { ret.push_back(tmp); return; } if ( begin>end ) return; int pre = candidates[begin]-1; for ( int i=begin; i<=end; ++i ) { if ( pre==candidates[i]) continue; pre = candidates[i]; tmp.push_back(candidates[i]); Solution::dfs(ret, tmp, candidates, i+1, end, target-candidates[i]); tmp.pop_back(); } }};

转载于:https://www.cnblogs.com/xbf9xbf/p/4536020.html

你可能感兴趣的文章

千元机自拍新体验，vivo Z3是你会拍照的“男朋友”