Combination Sum

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> out;
        vector<int> path;
        function<void(int,int)> dfs = [&](int start, int remain) {
            if (remain == 0) { out.push_back(path); return; }
            for (int i = start; i < (int)candidates.size(); ++i) {
                if (candidates[i] > remain) continue;
                path.push_back(candidates[i]);
                dfs(i, remain - candidates[i]); // reuse same i
                path.pop_back();
            }
        };
        dfs(0, target);
        return out;
    }
};

func combinationSum(candidates []int, target int) [][]int {
    out := [][]int{}
    path := []int{}
    var dfs func(start, remain int)
    dfs = func(start, remain int) {
        if remain == 0 {
            cp := make([]int, len(path))
            copy(cp, path)
            out = append(out, cp)
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remain {
                continue
            }
            path = append(path, candidates[i])
            dfs(i, remain-candidates[i])
            path = path[:len(path)-1]
        }
    }
    dfs(0, target)
    return out
}

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        out: List[List[int]] = []
        path: List[int] = []

        def dfs(start: int, remain: int) -> None:
            if remain == 0:
                out.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remain:
                    continue
                path.append(candidates[i])
                dfs(i, remain - candidates[i])
                path.pop()

        dfs(0, target)
        return out

var combinationSum = function(candidates, target) {
    const out = [];
    const path = [];
    const dfs = (start, remain) => {
        if (remain === 0) {
            out.push(path.slice());
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) continue;
            path.push(candidates[i]);
            dfs(i, remain - candidates[i]);
            path.pop();
        }
    };
    dfs(0, target);
    return out;
};

class Solution {
    private List<List<Integer>> out = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        dfs(0, target);
        return out;
    }

    private void dfs(int start, int remain) {
        if (remain == 0) {
            out.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) continue;
            path.add(candidates[i]);
            dfs(i, remain - candidates[i]);
            path.remove(path.size() - 1);
        }
    }
}

function combinationSum(candidates: number[], target: number): number[][] {
    const out: number[][] = [];
    const path: number[] = [];
    const dfs = (start: number, remain: number): void => {
        if (remain === 0) {
            out.push(path.slice());
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) continue;
            path.push(candidates[i]);
            dfs(i, remain - candidates[i]);
            path.pop();
        }
    };
    dfs(0, target);
    return out;
}