Generating All Subsets of a List Recursively

Functional Programming

Tutorial

The Problem

The power set of a set with n elements contains 2ⁿ subsets. Generating all subsets is fundamental to combinatorial algorithms: exhaustive search, constraint satisfaction, feature selection in machine learning, and generating test cases. The recursive insight is elegant — for each element, either include it or exclude it, then recurse on the rest. This divide-and-conquer structure maps directly onto functional recursion.

🎯 Learning Outcomes

• Understand the recursive structure of subset generation (include/exclude branching)

• Learn how to accumulate results across recursive branches in Rust

• See how the exponential output size (2ⁿ) relates to the linear depth of recursion

• Practice returning Vec<Vec<T>> from recursive functions correctly

Code Example

#![allow(clippy::all)]
// placeholder

let rec powerset = function
  | [] -> [[]]
  | x :: rest ->
    let ps = powerset rest in
    ps @ List.map (fun s -> x :: s) ps

let () =
  let sets = powerset [1; 2; 3] in
  Printf.printf "%d subsets:\n" (List.length sets);
  List.iter (fun s ->
    Printf.printf "{%s}\n" (String.concat "," (List.map string_of_int s))
  ) sets

Key Differences

Cloning cost: OCaml's persistent lists share tails, so x :: s is O(1); Rust must clone() each subset to add an element, making it O(k) per subset.

Pattern matching: OCaml's | [] -> ... | x :: rest -> is the canonical idiom; Rust uses if let Some((first, rest)) = slice.split_first().

Output type: OCaml returns 'a list list; Rust returns Vec<Vec<T>> with explicit Clone bound on T.

Accumulator style: Rust often uses extend to combine result vectors; OCaml uses @ (list append) naturally.

OCaml Approach

OCaml's idiomatic solution uses pattern matching and list comprehension style:

let rec subsets = function
  | [] -> [[]]
  | x :: rest ->
    let without = subsets rest in
    let with_x = List.map (fun s -> x :: s) without in
    without @ with_x

OCaml lists are persistent and cheap to prepend, so x :: s costs O(1). The garbage collector manages all the shared list structure automatically.

Full Source

#![allow(clippy::all)]
// placeholder

let rec powerset = function
  | [] -> [[]]
  | x :: rest ->
    let ps = powerset rest in
    ps @ List.map (fun s -> x :: s) ps

let () =
  let sets = powerset [1; 2; 3] in
  Printf.printf "%d subsets:\n" (List.length sets);
  List.iter (fun s ->
    Printf.printf "{%s}\n" (String.concat "," (List.map string_of_int s))
  ) sets

Deep Comparison

Exercises

Generate all subsets of [1, 2, 3, 4] and verify there are exactly 16 (2⁴) subsets including the empty set.

Modify the function to generate only subsets of a fixed size k (combinations C(n, k)).

Add a filter predicate parameter so only subsets satisfying a condition (e.g., sum > threshold) are returned.

Open Source Repos

functional-rust

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

Rust