1065 Intermediate

1065-combinations-sum — Combination Sum

Functional Programming

Tutorial

The Problem

Find all combinations of numbers from a given set that sum to a target, where each number may be used multiple times. This is a backtracking enumeration problem with applications in change-making (all ways to make an amount), spell correction (all word sequences summing to a score), and exam scheduling (all subsets hitting exactly N hours).

The key pruning: sort candidates and break early when the current candidate exceeds the remaining target — this transforms exponential worst case into practical tractability.

🎯 Learning Outcomes

• Implement combination sum using backtracking with reuse

• Sort candidates to enable early termination (pruning)

• Understand the difference from the no-reuse variant (combinations II)

• Return all combinations in canonical form (no duplicates from different orderings)

• Connect to the complete search / generate-and-prune paradigm

Code Example

#![allow(clippy::all)]
// 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
}

#[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"

Key Differences

Mutation vs accumulation: Rust uses current.push(c) / current.pop() in-place; OCaml prepends c :: current creating new lists at each step.

Sorting: Both sort before backtracking to enable pruning; Rust sorts in place with candidates.sort(), OCaml uses List.sort compare.

Index tracking: Rust uses an explicit start: usize parameter; OCaml uses List.iteri with an index comparison — less clean.

**itertools**: The itertools crate provides (0..n).combinations(k) for non-reuse combinations; Rust has no built-in for the reuse variant.

OCaml Approach

let combination_sum candidates target =
  let candidates = List.sort compare candidates in
  let results = ref [] in
  let rec backtrack start remaining current =
    if remaining = 0 then results := List.rev current :: !results
    else
      List.iteri (fun i c ->
        if i >= start && c <= remaining then
          backtrack i (remaining - c) (c :: current)
      ) candidates
  in
  backtrack 0 target [];
  !results

The structure is identical. OCaml's list prepend and List.rev at collection mirrors Rust's Vec::push and Vec::clone.

Full Source

#![allow(clippy::all)]
// 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
}

#[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"

✓ Tests Rust test suite

#[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]));
    }
}

Deep 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]`

Exercises

Implement combination_sum_no_reuse(candidates: &mut [i32], target: i32) -> Vec<Vec<i32>> where each number can be used at most once (sort + skip duplicates).

Write combination_sum_count(candidates: &[i32], target: i32) -> usize that counts the number of combinations without collecting them.

Add a max_depth: usize parameter that limits the maximum number of elements in any single combination.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust