本文共 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;}
代码主要包含以下几个部分：
void cb2help 函数：这是回溯法的核心函数，负责从当前位置开始，尝试所有可能的数值组合。combinationSum2 函数：这是最终的入口函数，负责对数组进行排序并调用回溯函数。需要注意的点是：当当前层的数值与前一个数值相同时，会跳过。这样可以避免重复计算相同的组合数。
回溯法的时间复杂度主要取决于组合数的数量级。如果目标组合数较小，回溯法的效率较高；但如果目标组合数较多，可能会导致性能问题。
转载地址：http://erfx.baihongyu.com/