Day64 代码随想录打卡|回溯算法篇---组合总和

题目(leecode T39):

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

方法:本题中的每个元素可以重复使用,且最终结果中的元素个数是未定的,只要满足和的条件即可,因此就决定了本题的深度是未定的,我们的终止条件就是path中的总和达到了targetsum值或者大于了targetsum值就终止了。如何等于的话就收集path中的结果。

1:传入参数与返回值:传入候选输入的数字candiates,还有目标值target,当前总和值sum,还有控制索引开始位置的startindex。

2:终止条件:终止条件是当sum值等于target或者是大于target值时终止。

3:单层处理逻辑:获取下一个处理的数字,开始递归并回溯。这里需要注意的是因为我们的数字是可以重复选取使用的,因此,startindex的值不用每次都加一,可以重复使用当前的数字。

题解:
 

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex){
        if(sum > target) return;                                //终止条件
        if(sum == target) {
            result.push_back(path);
            return;
            }
        for(int i = startIndex; i < candidates.size(); i++){    //单层处理逻辑
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        path.clear();
        result.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};
上一篇:SQL Server数据库的组成


下一篇:徒手绘制 Android 通用进度条-参数说明