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.

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]
]

Difficulty: Mediaum

这道题求数组中的某几个数之和等于一个给定的数,数组中的数可以重复使用.这道题有点像剑指offer中二叉树中和为某一值的路径.思路都差不多.需要写一个递归函数.

class Solution {
public:
    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++) {
                solution.push_back(candidates[i]);
                findSum(candidates, i, target-candidates[i], solution, res);
                solution.pop_back();
            }
        }
    }
};
 
comments powered by Disqus