本文主要是介绍194.回溯算法:组合总和||(力扣),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码解决
class Solution { public:vector<int> res; // 当前组合的临时存储vector<vector<int>> result; // 存储所有符合条件的组合// 回溯函数void backtracing(vector<int>& candidates, int target, int flag, int index, vector<bool>& used) {// 如果当前组合的和超过了目标值,则返回if (flag > target) return;// 如果当前组合的和等于目标值,则将当前组合加入结果集if (flag == target) {result.push_back(res);return;}// 遍历候选数组for (int i = index; i < candidates.size() && flag + candidates[i] <= target; i++) {// 如果当前元素和上一个元素相同且上一个元素没有被使用,跳过以避免重复组合if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue;}// 更新当前组合和flag += candidates[i];// 将当前元素加入当前组合res.push_back(candidates[i]);// 标记当前元素已使用used[i] = true;// 递归调用回溯函数,当前索引右移一位backtracing(candidates, target, flag, i + 1, used);// 回溯,移除当前元素used[i] = false;res.pop_back();flag -= candidates[i];}}// 主函数vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false); // 标记数组,用于记录元素是否已被使用sort(candidates.begin(), candidates.end()); // 排序输入数组backtracing(candidates, target, 0, 0, used); // 初始调用回溯函数return result; // 返回所有符合条件的组合} };
测试用例
输入
vector<int> candidates = {10, 1, 2, 7, 6, 1, 5}; int target = 8;
输出
[ [1, 1, 6], [1, 2, 5], [1, 7], [2, 6] ]
过程描述
初始状态:
candidates = {1, 1, 2, 5, 6, 7, 10}
(排序后)target = 8
res = []
(当前组合为空)result = []
(所有符合条件的组合为空)used = {false, false, false, false, false, false, false}
(所有元素未使用)递归回溯:
- 从第一个元素
1
开始:
flag = 1
,res = [1]
,继续递归。- 再次选择
1
:
flag = 2
,res = [1, 1]
,继续递归。- 选择
6
:
flag = 8
,res = [1, 1, 6]
,符合目标值,将组合加入result
,回溯,移除6
。- 选择
2
:
flag = 4
,res = [1, 1, 2]
,继续递归。- 选择
5
:
- 超过目标值,回溯,移除
2
。- 选择
5
,6
,7
,10
:
- 超过目标值,回溯。
- 选择
2
:
flag = 3
,res = [1, 2]
,继续递归。- 选择
5
:
flag = 8
,res = [1, 2, 5]
,符合目标值,将组合加入result
,回溯,移除5
。- 选择
6
,7
,10
:
- 超过目标值,回溯。
- 选择
6
:
flag = 7
,res = [1, 6]
,继续递归。- 选择
7
,10
:
- 超过目标值,回溯。
- 选择
7
:
flag = 8
,res = [1, 7]
,符合目标值,将组合加入result
,回溯,移除7
。- 选择
10
:
- 超过目标值,回溯。
- 选择
2
:
flag = 2
,res = [2]
,继续递归。- 选择
6
:
flag = 8
,res = [2, 6]
,符合目标值,将组合加入result
,回溯,移除6
。- 选择
7
,10
:
- 超过目标值,回溯。
- 选择
5
:
flag = 5
,res = [5]
,继续递归。- 选择
6
,7
,10
:
- 超过目标值,回溯。
这篇关于194.回溯算法:组合总和||(力扣)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!