Combinations

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> out;
        vector<int> path;
        function<void(int)> dfs = [&](int start) {
            if ((int)path.size() == k) { out.push_back(path); return; }
            int need = k - path.size();
            for (int i = start; i <= n - need + 1; ++i) {
                path.push_back(i);
                dfs(i + 1);
                path.pop_back();
            }
        };
        dfs(1);
        return out;
    }
};

func combine(n int, k int) [][]int {
    out := [][]int{}
    path := []int{}
    var dfs func(start int)
    dfs = func(start int) {
        if len(path) == k {
            tmp := make([]int, k)
            copy(tmp, path)
            out = append(out, tmp)
            return
        }
        need := k - len(path)
        for i := start; i <= n-need+1; i++ {
            path = append(path, i)
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
    dfs(1)
    return out
}

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        out: List[List[int]] = []
        path: List[int] = []
        def dfs(start: int) -> None:
            if len(path) == k:
                out.append(path[:])
                return
            need = k - len(path)
            for i in range(start, n - need + 2):
                path.append(i)
                dfs(i + 1)
                path.pop()
        dfs(1)
        return out

function combine(n, k) {
    const out = [];
    const path = [];
    const dfs = (start) => {
        if (path.length === k) {
            out.push([...path]);
            return;
        }
        const need = k - path.length;
        for (let i = start; i <= n - need + 1; i++) {
            path.push(i);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(1);
    return out;
}

class Solution {
    private List<List<Integer>> out = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int n, k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        dfs(1);
        return out;
    }

    private void dfs(int start) {
        if (path.size() == k) {
            out.add(new ArrayList<>(path));
            return;
        }
        int need = k - path.size();
        for (int i = start; i <= n - need + 1; i++) {
            path.add(i);
            dfs(i + 1);
            path.remove(path.size() - 1);
        }
    }
}

function combine(n: number, k: number): number[][] {
    const out: number[][] = [];
    const path: number[] = [];
    const dfs = (start: number): void => {
        if (path.length === k) {
            out.push([...path]);
            return;
        }
        const need = k - path.length;
        for (let i = start; i <= n - need + 1; i++) {
            path.push(i);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(1);
    return out;
}