给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 对于给定的输入,保证和为 target 的不同组合数少于 150 个。
时间: 2023-03-31 07:01:05 浏览: 138
好的,这是一个关于找出数组中可以使数字和为目标数的所有不同组合的问题。这个问题可以使用回溯算法来解决。具体来说,我们可以从数组的第一个元素开始,依次尝试将其加入到组合中,然后递归地处理剩余的元素,直到找到了和为目标数的组合或者处理完了所有元素。如果找到了和为目标数的组合,就将其加入到结果列表中。最后返回结果列表即可。需要注意的是,由于数组中的同一个数字可以无限制重复被选取,因此在递归处理剩余元素时,仍然从当前元素开始处理,而不是从下一个元素开始。
以下是示例代码:
```
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> cur;
backtrack(candidates, target, , cur, res);
return res;
}
private:
void backtrack(vector<int>& candidates, int target, int start, vector<int>& cur, vector<vector<int>>& res) {
if (target == ) {
res.push_back(cur);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (candidates[i] <= target) {
cur.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], i, cur, res);
cur.pop_back();
}
}
}
};
```
阅读全文