0039. Combination Sum.md

C++

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;

        function<void(int, int)> backtrack = [&](int start, int target) {
            if(target == 0) {
                res.push_back(path);
                return;
            }
            for(int i = start; i < candidates.size(); i++) {
                if(candidates[i] > target) continue;
                path.push_back(candidates[i]);
                backtrack(i, target - candidates[i]);
                path.pop_back();
            }
        };

        backtrack(0, target);
        return res;
    }
};

JavaScript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    // Sort the candidates array as otherwise we could 
    // come up with solution [3,2,2] instead of [2,2,3]
    candidates.sort((a,b) =>  a - b);
    
    // Store all possible combinations in here
    let stack = [];
    
     // The recursive part. 
    // target is what we're looking for. This will become smaller, deeper in to the recursive calls
    // res is where we will record our current path
    // i is the index of the numbers we're considering. Once we get stuck with the 2's
    // we will increase i to try other combinations
    function dfs(target, res, i) {
        if (target === 0) {
            stack.push(res);
            return;
        }  else {
             // don't run over the candidates array length 
            // and don't try candidates that would bring target below 0
            while (i < candidates.length && target - candidates[i] >= 0) {
                dfs(target - candidates[i], [...res, candidates[i]], i)
                i++;
            }   
        }
    }
    dfs(target, [], 0);
    return stack;
};