39. Combination Sum
Medium
260179FavoriteShare
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.Example 1:
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ]Example 2:
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]Accepted
415,019
Submissions
805,772
参考文章https://zxi.mytechroad.com/blog/searching/leetcode-39-combination-sum/
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> rt; vector<int> temp; sort(candidates.begin(),candidates.end()); dfs(0,rt,temp,target,candidates); return rt; } private: void dfs(int index,vector<vector<int>>& rt,vector<int>& temp,int target,vector<int>& candidates){ if(0==target){ rt.push_back(temp); return; } for(int i=index;i<candidates.size();i++){ if (candidates[i] > target) break; temp.push_back(candidates[i]); dfs(i,rt,temp,target-candidates[i],candidates);//这里的i还是i，表明可以重复取 temp.pop_back(); } } };
