如何申请建设网站首页,网站建设服务器价格,专业的外贸行业网站开发,网站备案幕布申请题目来源#xff1a;https://leetcode.cn/problems/combination-sum/description/ C题解#xff1a; 递归法。递归前对数组进行有序排序#xff0c;可方便后续剪枝操作。
递归函数参数#xff1a;定义两个全局变量#xff0c;二维数组result存放结果集#xff0c;数组pa…题目来源https://leetcode.cn/problems/combination-sum/description/ C题解 递归法。递归前对数组进行有序排序可方便后续剪枝操作。
递归函数参数定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。参数为集合candidates和目标值target已有元素和sum及开始遍历的第ind个元素注意遍历时可以从ind开始不用1递归终止条件当sum大于target或sum等于target两种情况单层递归逻辑更新sum值进行回溯。
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(vectorint candidates, int target, int sum, int ind) {if(sum target) return;if(sum target) {res.push_back(path); return;}for(int i ind; i candidates.size(); i) {if(sum candidates[i] target) break;path.push_back(candidates[i]);backtracking(candidates, target, sum candidates[i], i);path.pop_back();}return;}vectorvectorint combinationSum(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());if(candidates[0] target) return res;backtracking(candidates, target, 0, 0);return res;}
};
