题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
算法1
DFS 暴力遍历
根据题目意义 所有元素独一无二
数据量偏小
对于一个包含不同元素的集合 {A,B,C,D}
我们对于每个元素逐个尝试
比如
A A A A A
A A A B
A B B B
A B C C
等
只要相加不得和不大于target即可进行尝试
剩下的就是保证 dfs过程不重不漏
为了避免 选择A后再选择B又回头选择A 那么ABA
和AAB就造成重复
所以每次DFS会规定选择集合的起点idx
C++ 代码
class Solution {
public:
vector<vector<int>> ans;
vector<int> v;
int sum;
void dfs(const vector<int>& candidates,const int target,int idx){
if(sum > target || idx >= candidates.size()) return;
else if(sum == target){
ans.push_back(v);return;
}
for(int i = idx; i < candidates.size();i++){
sum += candidates[i];
v.push_back(candidates[i]);
dfs(candidates,target,i);
sum -= candidates[i];
v.pop_back();
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> v; sum = 0;
dfs(candidates,target,0);
return ans;
}
};
