leetcode-39.cpp

class Solution {
public:
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<std::vector<int>>> dp(target + 1);

        for (int i = 0; i < candidates.size(); i++) {
            for (int j = 0; j <= target; j++) {
                if (j == candidates[i]) {
                    dp[j].push_back(std::vector<int>{candidates[i]});
                } else if (j > candidates[i]) {
                    for (auto& e : dp[j - candidates[i]]) {
                        dp[j].push_back(e);
                        dp[j].back().push_back(candidates[i]);
                    }
                }
            }
        }

        return dp[target];
    }
};