# [39\. Combination Sum](https://leetcode.com/problems/combination-sum/)

:::spoiler Solution

class Solution {
private:
    vector<vector<int>> res;
    vector<int> comb;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        backtracking(candidates, target, 0);
        return res;
    }
    void backtracking(vector<int>& candidates, int target, int start)
    {
        if (target == 0) res.push_back(comb);
        if (target < 0) return;

        for (int i = start; i < candidates.size(); i++)
        {
            comb.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i);
            comb.pop_back();
        }
    }
};

- T: $O(N^{\frac{T}{M}+1})$
- S: $O(\frac{T}{M})$
:::