Combinations

Backtracking

74.2% acceptance

Jan 12, 2026

8883

253

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    fn binomial(n: usize, k: usize) -> usize {
      if k > n { return 0; }
      if k == 0 || k == n { return 1; }
      let k = k.min(n - k);
      (1..=k).fold(1, |acc, i| acc * (n - k + i) / i)
    }
    
    let mut result = Vec::with_capacity(binomial(n as usize, k as usize));
    let mut path = Vec::with_capacity(k as usize);
    Self::dfs(1, n, k, &mut path, &mut result);
    result
  }
  
  fn dfs(start: i32, n: i32, k: i32, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if path.len() == k as usize {
      result.push(path.clone());
      return;
    }
    
    for i in start..=n - (k - path.len() as i32) + 1 {
      path.push(i);
      Self::dfs(i + 1, n, k, path, result);
      path.pop();
    }
  }
}