组合总和——力扣39

题目描述

回溯

class Solution {
public:vector<vector<int>> res;vector<int> seq; void dfs(vector<int>& nums, int pos, int target){if(target==0){res.emplace_back(seq);return;}if(pos==nums.size()){return;}//直接跳过dfs(nums, pos+1, target);if(target - nums[pos]>=0){seq.push_back(nums[pos]);dfs(nums, pos, target-nums[pos]);seq.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target){dfs(candidates, 0, target);return res;}
};