🎬 Error Handling in Rust Option, Result, the ? operator, and combinators.

📝 Text version (for readers / accessibility)

• Option represents a value that may or may not exist — Some(value) or None

• Result represents success (Ok) or failure (Err) — no exceptions needed

• The ? operator propagates errors up the call stack concisely

• Combinators like .map(), .and_then(), .unwrap_or() chain fallible operations

• The compiler forces you to handle every error case — no silent failures

1065: Combination Sum

Difficulty: Intermediate Category: Backtracking Concept: Find all unique combinations of candidates that sum to a target, where each number can be reused Key Insight: Starting each recursion at index `i` (not `i+1`) allows reuse; sorting enables early pruning when `candidates[i] > remaining`. The variant with `i+1` and duplicate skipping solves Combination Sum II.

// 1065: Combination Sum — Find Combos Summing to Target

// Approach 1: Backtracking with reuse allowed
fn combination_sum(candidates: &mut Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    candidates.sort();
    let mut results = Vec::new();
    let mut current = Vec::new();

    fn backtrack(
        start: usize, remaining: i32,
        candidates: &[i32], current: &mut Vec<i32>, results: &mut Vec<Vec<i32>>,
    ) {
        if remaining == 0 {
            results.push(current.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] > remaining { break; } // sorted, so prune
            current.push(candidates[i]);
            backtrack(i, remaining - candidates[i], candidates, current, results);
            current.pop();
        }
    }

    backtrack(0, target, candidates, &mut current, &mut results);
    results
}

// Approach 2: Functional with iterators
fn combination_sum_func(candidates: &[i32], target: i32) -> Vec<Vec<i32>> {
    let mut sorted = candidates.to_vec();
    sorted.sort();

    fn solve(start: usize, remaining: i32, sorted: &[i32]) -> Vec<Vec<i32>> {
        if remaining == 0 { return vec![vec![]]; }
        if remaining < 0 { return vec![]; }
        let mut results = Vec::new();
        for i in start..sorted.len() {
            if sorted[i] > remaining { break; }
            for mut combo in solve(i, remaining - sorted[i], sorted) {
                combo.insert(0, sorted[i]);
                results.push(combo);
            }
        }
        results
    }

    solve(0, target, &sorted)
}

// Approach 3: Combination sum II (each number used once)
fn combination_sum_unique(candidates: &mut Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    candidates.sort();
    let mut results = Vec::new();
    let mut current = Vec::new();

    fn backtrack(
        start: usize, remaining: i32,
        candidates: &[i32], current: &mut Vec<i32>, results: &mut Vec<Vec<i32>>,
    ) {
        if remaining == 0 {
            results.push(current.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] > remaining { break; }
            if i > start && candidates[i] == candidates[i - 1] { continue; } // skip dupes
            current.push(candidates[i]);
            backtrack(i + 1, remaining - candidates[i], candidates, current, results);
            current.pop();
        }
    }

    backtrack(0, target, candidates, &mut current, &mut results);
    results
}

fn main() {
    let mut cands = vec![2, 3, 6, 7];
    let results = combination_sum(&mut cands, 7);
    println!("Combinations summing to 7: {:?}", results);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_combination_sum() {
        let mut cands = vec![2, 3, 6, 7];
        let r = combination_sum(&mut cands, 7);
        assert_eq!(r.len(), 2);
        assert!(r.contains(&vec![2, 2, 3]));
        assert!(r.contains(&vec![7]));
    }

    #[test]
    fn test_combination_sum_func() {
        let r = combination_sum_func(&[2, 3, 5], 8);
        assert_eq!(r.len(), 3);
    }

    #[test]
    fn test_combination_sum_unique() {
        let mut cands = vec![10, 1, 2, 7, 6, 1, 5];
        let r = combination_sum_unique(&mut cands, 8);
        assert!(r.contains(&vec![1, 1, 6]));
        assert!(r.contains(&vec![1, 2, 5]));
        assert!(r.contains(&vec![1, 7]));
        assert!(r.contains(&vec![2, 6]));
    }
}

(* 1065: Combination Sum — Find Combos Summing to Target *)

(* Approach 1: Backtracking with reuse allowed *)
let combination_sum candidates target =
  let sorted = List.sort compare candidates in
  let results = ref [] in
  let rec backtrack start current remaining =
    if remaining = 0 then
      results := List.rev current :: !results
    else if remaining > 0 then
      List.iteri (fun idx c ->
        if idx >= start && c <= remaining then
          backtrack idx (c :: current) (remaining - c)
      ) sorted
  in
  backtrack 0 [] target;
  List.rev !results

(* Approach 2: Functional with list accumulation *)
let combination_sum_func candidates target =
  let sorted = List.sort compare candidates in
  let rec solve start remaining =
    if remaining = 0 then [[]]
    else if remaining < 0 then []
    else
      List.filteri (fun i _ -> i >= start) sorted
      |> List.concat_map (fun (c : int) ->
        if c > remaining then []
        else
          let idx = List.filteri (fun i _ -> i >= start) sorted
                    |> List.mapi (fun i x -> (i + start, x))
                    |> List.find (fun (_, x) -> x = c)
                    |> fst in
          List.map (fun rest -> c :: rest) (solve idx (remaining - c))
      )
  in
  solve 0 target

(* Approach 3: Array-based for efficiency *)
let combination_sum_arr candidates target =
  let arr = Array.of_list (List.sort compare candidates) in
  let n = Array.length arr in
  let results = ref [] in
  let current = ref [] in
  let rec backtrack start remaining =
    if remaining = 0 then
      results := List.rev !current :: !results
    else
      for i = start to n - 1 do
        if arr.(i) <= remaining then begin
          current := arr.(i) :: !current;
          backtrack i (remaining - arr.(i));
          current := List.tl !current
        end
      done
  in
  backtrack 0 target;
  List.rev !results

let () =
  let r1 = combination_sum [2; 3; 6; 7] 7 in
  assert (List.length r1 = 2);  (* [2;2;3] and [7] *)

  let r2 = combination_sum [2; 3; 5] 8 in
  assert (List.length r2 = 3);  (* [2;2;2;2], [2;3;3], [3;5] *)

  let r3 = combination_sum_arr [2; 3; 6; 7] 7 in
  assert (List.length r3 = 2);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Combination Sum — Comparison

Core Insight

Combination sum is backtracking with an index parameter controlling reuse. Starting at `i` (not `i+1`) allows the same element to be picked again. Sorting enables pruning: if `candidates[i] > remaining`, all later candidates are too large.

OCaml Approach

`List.sort compare` for sorting candidates
`List.iteri` with index filtering for start position
Prepend `::` + `List.rev` for result building
`ref` list for accumulating results

Rust Approach

`sort()` in-place on `Vec`
`break` in sorted loop for pruning — cleaner than filtering
`push`/`pop` on current for backtracking
Variant: `continue` for duplicate skipping in Combination Sum II

Comparison Table

Aspect	OCaml	Rust
Sorting	`List.sort compare` (returns new list)	`.sort()` (in-place)
Pruning	Index filtering with `List.iteri`	`break` in sorted loop
Result building	Prepend `::` + `List.rev`	`push` + `pop`
Reuse control	Recurse with same index	Recurse with same `i`
Dedup (variant)	Would need explicit skip	`if i > start && arr[i] == arr[i-1]`