56.组合总数

1.题目描述

示例 1：

输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。

示例 2：

输入:candidates = [2,3,5], target = 8输出:[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入:candidates = [2], target = 1输出:[]

2.代码

class Solution { public: vector<vector<int>> res; vector<int> curcomb; int sum = 0; void backtrack(vector<int>& candidates,vector<int> curcomb,vector<vector<int>> res,int target,int index){ if(sum == target || index==candidates.size()){ res.push_back(sum); return ;//回溯，弹出尾元素继续循环 } for() { curcomb.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { if(candidates.size()==0){ return {}; } backtrack(candidates,curcomb,res,target,index); return res; } };