LeetCode#40组合总和Ⅱ
题目：
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
来源：力扣（LeetCode）
链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
vector<vector<int>>ans;
vector<int>temp;
void dfs(vector<int>& candidates,int target,int pos,int sum)
{
if(sum == target)
{
for(int i = 0 ; i < ans.size() ; i ++)
{
if(temp == ans[i])
return;
}
ans.push_back(temp);
return;
}
if(sum > target)
return;
if(pos >= candidates.size())
return;
temp.push_back(candidates[pos]);
dfs(candidates,target,pos+1,sum+candidates[pos]);
temp.pop_back();
dfs(candidates,target,pos+1,sum);
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(candidates,target,0,0);
return ans;
}
};
|
这本来是一道很简单的递归回溯问题，但是因为题目要求不能包含重复的题解，所以对于我这个菜鸡一下就难了起来…通过对stl库的了解发现，sort是可以直接用来排序简单形式的vector的（按照字典序排列），且vector本身是可以使用标准运算符（如== > <等等进行比较的，仅限简单数据类型）
（鸽了好久的博客终于要开始更了）
（咕咕咕）
