题目

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

分析

又是一个所有满足条件的排列组合,还是用我们熟悉的递归,我的递归是弱项,所以我会多练习一些这方面的题。这里我们新加入三个变量,start记录当前的递归到的下标,out为一个解,res保存所有已经得到的解,每次调用新的递归函数时,此时的target要减去当前数组的的数,具体看代码如下:

我们也可以用迭代的解法来做,建立一个三维数组dp,这里dp[i]表示目标数为i的所有解法集合。这里的i就从1遍历到target即可,对于每个i,我们都新建一个二维数组cur,然后遍历candidates数组,如果遍历到的数字大于i,说明当前及之后的数字都无法组成i,直接break掉。否则如果相等,那么把当前数字自己组成一个数组,并且加到cur中。否则就遍历dp[i - candidates[j] - 1] 中的所有数组,如果当前数字大于数组的首元素,则跳过,因为我们的结果要求是要有序的。否则就将当前数字加入数组的开头,并且将数组放入cur之中即可,参见代码如下

代码

初始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
combinationSumDFS(candidates, target, 0, {}, res);
return res;
}
void combinationSumDFS(vector<int> &candidates, int target, int start, vector<int> out, vector<vector<int>> &res) {
if (target < 0)
return;
else if (target == 0) {
res.push_back(out);
return;
}
for (int i = start; i < candidates.size(); ++i) {
out.push_back(candidates[i]);
combinationSumDFS(candidates, target - candidates[i], i, out, res);
out.pop_back();
}
}
};

迭代三维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
vector<vector<vector<int>>> dp;
sort(candidates.begin(), candidates.end());
for (int i = 1; i <= target; ++i) {
vector<vector<int>> cur;
for (int j = 0; j < candidates.size(); ++j) {
if (candidates[j] > i) break;
else if (candidates[j] == i) {cur.push_back({candidates[j]}); continue;}
for (auto a : dp[i - candidates[j] - 1]) {
if (candidates[j] > a[0]) continue;
a.insert(a.begin(), candidates[j]);
cur.push_back(a);
}
}
dp.push_back(cur);
}
return dp[target - 1];
}
};

分析

其实思路都是一样的,主要找准利用移位操作来实现除法操作。详细见思路部分。