Leetcode 39 Solution

This article provides solution to leetcode question 39 (combination-sum).
Categories:
Tags:
Access this page by simply typing in "lcs 39" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/combination-sum

Solution

class Solution {
    vector<int> cur;
    vector<vector<int>> res;

public:
    void combinationSum(vector<int>& candidates, int target, int cur_sum, int from) {
        if (cur_sum > target)
            return;
        else if (cur_sum == target)
        {
            res.push_back(cur);
            return;
        }
        
        for (int i = from; i < candidates.size(); i++)
        {
            int v = candidates[i];
            cur.push_back(v);
            combinationSum(candidates, target, cur_sum + v, i);
            cur.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        combinationSum(candidates, target, 0, 0);
        return res;
    }
};