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

回溯法是解决组合数问题的一种高效方法。以下是基于回溯法实现的组合数问题解决方案：

#include 
   
    #include 
    
     using namespace std;void cb2help(vector
     
       &res, vector
      
        &v, int target, int i, vector
       
         &recp) {    if (target < 0) return;    if (target == 0) {        res.push_back(recp);        return;    }    for (unsigned int k = i; k < v.size(); ++k) {        if (k > i && v[k] == v[k-1]) continue;        recp.push_back(v[k]);        cb2help(res, v, target - v[k], k + 1, recp);        recp.pop_back();        if (target - v[k] < 0) return;    }}vector
        
          combinationSum2(vector
         
           v, int target) { sort(v.begin(), v.end()); vector
          
            res; vector
           
             recp; cb2help(res, v, target, 0, recp); return res;}
           
          
         
        
       
      
     
    
   

代码主要包含以下几个部分：

需要注意的点是：当当前层的数值与前一个数值相同时，会跳过。这样可以避免重复计算相同的组合数。

回溯法的时间复杂度主要取决于组合数的数量级。如果目标组合数较小，回溯法的效率较高；但如果目标组合数较多，可能会导致性能问题。

转载地址：http://erfx.baihongyu.com/