Combination Sum
最后更新于：2022-04-01 22:57:33
**一. 题目描述**
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
• All numbers (including target) will be positive integers.
• Elements in a combination (a1; a2; … ; ak) must be in non-descending order. (a1<=a2<=…<= ak).
• The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7, A solution set is:
~~~
[7]
[2, 2, 3]
~~~
**二. 题目分析**
题目大意是：有一个正整数集合C和一个正整数目标T。现从C中选出一些数，使其累加和恰好等于T（C中的每个数都可以取若干次），求所有不同的取数方案，是一道典型的深度优先搜索题。
题目的一个细节是，正整数集合C可能存在**重复的数**，而这些数用于组合时，会产生重复的排列组合，如下图所示，而题目要求：The solution set must not contain duplicate combinations.
我的解决方法是对正整数集合C先进行从小到大排序，然后使用vector的erase方法去除集合C的重复元素，然后再进行DFS的相关运算。
**三. 示例代码**
~~~
#include
#include
#include
using namespace std;
class Solution
{
public:
vector > combinationSum(vector &candidates, int target)
{
vector temp; // 用于存放临时组合
sort(candidates.begin(), candidates.end());
// 结果要求输出的组合不能重复，需要去除candidates中的重复元素
candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
combinationDFS(candidates, temp, 0, target);
return result;
}
private:
vector > result;
void combinationDFS(vector &candidates, vector &temp, size_t index, int target)
{
if (target == 0) // 得到满足目标的一组解
{
result.push_back(temp);
return;
}
else
{
for (size_t i = index; i < candidates.size(); ++i)
{
if (candidates[i] > target)
return;
temp.push_back(candidates[i]);
combinationDFS(candidates, temp, i, target - candidates[i]);
temp.pop_back();
}
}
}
};
~~~
**四. 小结**
该题是一道经典的DFS题目，后续还有Combination Sum II和Combination Sum III，需要深入研究。
';