题目描述：
给出一个没有重复元素的长度为 $ n $ 整数数组candidates和一个目标整数target，找出能够使数字和为目标数target的所有不同组合，并返回。
其中candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
数据范围：
$ 1\le n \le 30, 2\le candidates[i] \le 40 $
题解：
类似完全背包，也类似组合数。每个元素可以取或不取。取的话可以继续从当前位置开始继续取或不取。不取的话就从下一个位置开始。
代码：
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
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
void dfs(int step, int sum, int target, vector<int> &cur, vector<int> &nums)
{
if (sum == target)
{
ans.emplace_back(cur);
return;
}
if (sum > target)
return;
if (step == nums.size())
return;
cur.emplace_back(nums[step]);
dfs(step, sum + nums[step], target, cur, nums);
cur.pop_back();
dfs(step + 1, sum, target, cur, nums);
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
vector<int> cur;
dfs(0, 0, target, cur, candidates);
return ans;
}
};
|