题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
题解
有一说一，我是真的不喜欢递归。
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
| vector<vector<int>>res = {};
vector<int> candidates1;
int mymin;
void dfs(int target, vector<int>& keepin,int index)
{
if (!target)
{
res.push_back(keepin);
return;
}
if (target < mymin)return;
for (int i=index;i<candidates1.size();i++)
{
keepin.push_back(candidates1[i]);
dfs(target - candidates1[i], keepin,i);
keepin.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
candidates1= candidates;
vector<int>::iterator myMin = min_element(candidates.begin(), candidates.end());
mymin = *myMin;
vector<int> keepin = {};
dfs(target, keepin,0);
return res;
}
|
问题描述
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
题解
和上面那道题的区别，不能有重复元素，那index每次就往前走一步，但问题是vector里面有重复元素，这样最后找出来的vector里面就会有重复的vector，暂时想到的方法是每找到一个vector，进行排序后加入set进行去重。
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
33
34
35
36
37
38
| class Solution {
set<vector<int>>res = {};
vector<int> candidates1;
int mymin;
int v_size;
vector<int> tmp;
void dfs(int target, vector<int>& keepin, int index)
{
if (!target)
{
tmp = keepin;
sort(tmp.begin(), tmp.end());
res.insert(tmp);
return;
}
if (target < mymin)return;
for (int i = index; i<v_size; i++)
{
keepin.push_back(candidates1[i]);
dfs(target - candidates1[i], keepin, i+1);
keepin.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
candidates1 = candidates;
vector<int>::iterator myMin = min_element(candidates.begin(), candidates.end());
mymin = *myMin;
v_size = candidates.size();
vector<int> keepin = {};
dfs(target, keepin, 0);
vector<vector<int>> v;
for (auto i = res.begin(); i != res.end(); i++)
v.push_back(*i);
return v;
}
};
|
浪费在去重上面的时间太多了，先对candidates排序，然后在回溯之前，对下一位数字判断，如果是相同的，就舍弃；因而不会有重复的集合出现。而且数据没有丢失，这是因为它的上个数在递归过程中能用到它（若它满足条件）。
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
33
34
35
36
37
38
| vector<vector<int>>res = {};
vector<int> candidates1;
int mymin,v_size;
void dfs(int target, vector<int>& keepin, int index)
{
if (!target)
{
res.push_back(keepin);
return;
}
if (target < mymin)return;
for (int i = index; i<v_size; i++)
{
keepin.push_back(candidates1[i]);
dfs(target - candidates1[i], keepin, i+1);
int j = i+1;
while (j < v_size)
{
if (candidates1[i] == candidates1[j])
i = j;
else
break;
j++;
}
keepin.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
candidates1 = candidates;
sort(candidates1.begin(), candidates1.end());
v_size = candidates.size();
if (!v_size)return res;
vector<int>::iterator myMin = min_element(candidates.begin(), candidates.end());
mymin = *myMin;
vector<int> keepin = {};
dfs(target, keepin, 0);
return res;
}
|