39-combination-sum.cpp

class Solution {
public:
    vector<int> cands;
    int evaluate(vector<int>& curr) {
        int sum = 0;
        for (int i = 0; i < curr.size(); i++) {
            sum += curr.at(i) * cands.at(i);
        }
        return sum;
    }
    vector<vector<int>> convert(vector<vector<int>> &results) {
        vector<vector<int>> answers;
        for (int row = 0; row < results.size(); row++) {
            vector<int> ans;
            for (int i = 0; i < results.at(row).size(); i++) {
                for (int j = 0; j < results.at(row).at(i); j++) {
                    ans.push_back(cands.at(i));
                }
            }
            answers.push_back(ans);
        }
        return answers;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        this->cands = candidates;
        vector<int> solution;
        vector<vector<int>> results;
        stack<vector<int>> sols;
        sols.push({});
        while (!sols.empty()) {
            vector<int> curr = sols.top();
            sols.pop();

            int value = evaluate(curr);
            if (value == target) {
                results.push_back(curr);
                continue;
            }
            if (value > target) {
                continue;
            }
            if (curr.size() == candidates.size()) {
                continue;
            }

            for (int i = 0; i <= target / (candidates.at(curr.size())); i++) {
                vector<int> c(curr);
                c.push_back(i);
                sols.push(c);
            }
        }
        return convert(results);
    }
};