题目描述

可以用无限次，组成目标target即可，返回这个组合，还有目标。

样例

candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

算法1

(DFS 回溯) $O(2^n)$

Python 代码

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        self.dfs(candidates, target, [], res)
        return res

    def dfs(self, nums, target, path, res):
        if target < 0:
            return 
        if target == 0:
            res.append(path)
            return 
        for i in range(len(nums)):
            self.dfs(nums[i:], target-nums[i], path+[nums[i]], res)

c++版

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int> > res;
        vector<int> combination;
        dfs(candidates, target, res, combination, 0);
        return res;
    }
private:
    void dfs(vector<int> &candidates, int target, vector<vector<int> > &res, vector<int> &combination, int begin) {
        if (!target) {
            res.push_back(combination);
            return;
        }
        for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) {
            combination.push_back(candidates[i]);
            dfs(candidates, target - candidates[i], res, combination, i);
            combination.pop_back();
        }
    }
};