1function backtrack(n: number, k: number, startIndex: number, path: number[], result: number[][]) {
2  if (path.length === k) {
3    result.push([...path]);
4    return;
5  }
6
7  for (let i = startIndex; i <= n; i++) {
8    path.push(i);
9    backtrack(n, k, i + 1, path, result);
10    path.pop();
11  }
12}
13
14/**
15 * #77, https://leetcode.cn/problems/combinations/
16 */
17export const Combine = (n: number, k: number): number[][] => {
18  const result: number[][] = [];
19  const path: number[] = [];
20  backtrack(n, k, 1, path, result);
21  return result;
22};

1// Problem: Combinations
2// url: https://leetcode.com/problems/combinations/
3#[allow(dead_code)]
4fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
5    let mut result = Vec::new();
6    let mut path = Vec::new();
7    backtracking(n, k, 1, &mut path, &mut result);
8    result
9}
10
11// p2: start point
12// p3: path
13// p4: result
14fn backtracking(p0: i32, p1: i32, p2: i32, p3: &mut Vec<i32>, p4: &mut Vec<Vec<i32>>) {
15    // base case
16    if p1 == 0 {
17        p4.push(p3.clone());
18        return;
19    }
20    // recursive case
21    for i in p2..=p0 {
22        p3.push(i);
23        backtracking(p0, p1 - 1, i + 1, p3, p4);
24        p3.pop();
25    }
26}

1function letterCombinations(digits: string): string[] {
2    const len = digits.length;
3    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
4    if (!len) {
5        return [];
6    }
7    if (len === 1) {
8        return map[digits].split("");
9    }
10    const ans = [];
11    const path = [];
12
13    function backtracking(n: string, k: number, startIndex: number) {
14        if (path.length === k) {
15            ans.push(path.join(''));
16            return;
17        }
18        for (const v of map[n[startIndex]]) {
19            path.push(v);
20            backtracking(n, k, startIndex + 1);
21            path.pop();
22        }
23    }
24
25    backtracking(digits, len, 0);
26    return ans;
27};