Combination sum 2

Array Backtracking

59.0% acceptance

Jan 12, 2026

12175

382

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut candidates = candidates;
    candidates.sort();
    let mut result = Vec::new();
    let mut current = Vec::new();
    Self::helper40(&candidates, target, 0, &mut current, &mut result);
    result
  }
  
  fn helper40(
    candidates: &Vec<i32>,
    target: i32,
    start: usize,
    current: &mut Vec<i32>,
    result: &mut Vec<Vec<i32>>,
  ) {
    if target == 0 {
      result.push(current.clone());
      return;
    }
    
    if target < 0 {
      return;
    }
    
    for i in start..candidates.len() {
      // Skip duplicates at the same level
      if i > start && candidates[i] == candidates[i - 1] {
        continue;
      }
      
      current.push(candidates[i]);
      // Each number can only be used once, so pass i+1
      Self::helper40(candidates, target - candidates[i], i + 1, current, result);
      current.pop();
    }
  }
}