39. Combination Sum 组合之和

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.


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:

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:

Difficulty: Mediaum


class Solution {
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> solution;
        findSum(candidates, 0, target, solution, res);
        return res;

    void findSum(vector<int>& candidates,int start,int target,vector<int>& solution,vector<vector<int>>& res){
        if (target<0) return;
        else if (target==0) res.push_back(solution);
        else {
            for (int i = start; i < candidates.size(); i++) {
                findSum(candidates, i, target-candidates[i], solution, res);
comments powered by Disqus