Combination sum iii

Array Backtracking

73.0% acceptance

Jan 12, 2026

6611

122

Find all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    Self::backtrack(k, n, 1, &mut path, &mut result);
    result
  }
  
  fn backtrack(k: i32, target: i32, start: i32, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
    if path.len() == k as usize {
      if target == 0 {
        result.push(path.clone());
      }
      return;
    }
    
    for i in start..=9 {
      if i > target { break; }
      path.push(i);
      Self::backtrack(k, target - i, i + 1, path, result);
      path.pop();
    }
  }
}