1066 Advanced

1066-subsets-power-set — Subsets / Power Set

Functional Programming

Tutorial

The Problem

The power set of a set S is the set of all subsets, including the empty set and S itself. A set with n elements has 2^n subsets. Generating all subsets is needed for exhaustive search, testing all combinations of feature flags, computing all possible teams from a player list, and in model checking for state space exploration.

Two elegant algorithms: backtracking (include/exclude each element) and bitmasking (each bit of an integer represents whether an element is included).

🎯 Learning Outcomes

• Generate all 2^n subsets using backtracking

• Generate subsets using bitmask enumeration over integers 0..2^n

• Understand the bijection between subsets and binary numbers

• Handle subsets with duplicates by sorting and skipping

• Connect to power set semantics in set theory and logic

Code Example

#![allow(clippy::all)]
// 1066: All Subsets (Power Set) — Backtracking vs Bitmasking

// Approach 1: Backtracking
fn subsets_backtrack(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    let mut current = Vec::new();

    fn build(start: usize, nums: &[i32], current: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
        results.push(current.clone());
        for i in start..nums.len() {
            current.push(nums[i]);
            build(i + 1, nums, current, results);
            current.pop();
        }
    }

    build(0, nums, &mut current, &mut results);
    results
}

// Approach 2: Bitmasking
fn subsets_bitmask(nums: &[i32]) -> Vec<Vec<i32>> {
    let n = nums.len();
    let total = 1 << n;
    (0..total)
        .map(|mask| {
            (0..n)
                .filter(|&i| mask & (1 << i) != 0)
                .map(|i| nums[i])
                .collect()
        })
        .collect()
}

// Approach 3: Iterative doubling (fold)
fn subsets_fold(nums: &[i32]) -> Vec<Vec<i32>> {
    nums.iter().fold(vec![vec![]], |acc, &x| {
        let mut result = acc.clone();
        for mut subset in acc {
            subset.push(x);
            result.push(subset);
        }
        result
    })
}

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

    #[test]
    fn test_backtrack() {
        let s = subsets_backtrack(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
        assert!(s.contains(&vec![]));
        assert!(s.contains(&vec![1, 2, 3]));
    }

    #[test]
    fn test_bitmask() {
        let s = subsets_bitmask(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
    }

    #[test]
    fn test_fold() {
        let s = subsets_fold(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
    }

    #[test]
    fn test_empty() {
        assert_eq!(subsets_backtrack(&[]).len(), 1);
    }
}

(* 1066: All Subsets (Power Set) — Backtracking vs Bitmasking *)

(* Approach 1: Backtracking *)
let subsets_backtrack nums =
  let n = Array.length nums in
  let results = ref [] in
  let current = ref [] in
  let rec build start =
    results := List.rev !current :: !results;
    for i = start to n - 1 do
      current := nums.(i) :: !current;
      build (i + 1);
      current := List.tl !current
    done
  in
  build 0;
  List.rev !results

(* Approach 2: Bitmasking *)
let subsets_bitmask nums =
  let n = Array.length nums in
  let total = 1 lsl n in
  List.init total (fun mask ->
    let subset = ref [] in
    for i = 0 to n - 1 do
      if mask land (1 lsl i) <> 0 then
        subset := nums.(i) :: !subset
    done;
    List.rev !subset
  )

(* Approach 3: Functional — iterative doubling *)
let subsets_fold nums =
  Array.fold_left (fun acc x ->
    acc @ List.map (fun subset -> subset @ [x]) acc
  ) [[]] nums

let () =
  let s1 = subsets_backtrack [|1; 2; 3|] in
  assert (List.length s1 = 8);
  assert (List.mem [] s1);
  assert (List.mem [1; 2; 3] s1);

  let s2 = subsets_bitmask [|1; 2; 3|] in
  assert (List.length s2 = 8);

  let s3 = subsets_fold [|1; 2; 3|] in
  assert (List.length s3 = 8);

  assert (List.length (subsets_backtrack [||]) = 1);

  Printf.printf "✓ All tests passed\n"

Key Differences

Recursive elegance: OCaml's subsets function is 3 lines using @ List.map; Rust's backtracking is more verbose but explicit.

Bitmask: Both languages express mask & (1 << i) != 0 identically — bitmasking is language-independent.

Memory: Rust's backtracking collects into Vec<Vec<i32>> explicitly; OCaml's recursive version builds lists naturally.

Lazy subsets: Rust can generate subsets lazily with a bitmasking iterator; OCaml's lazy Seq version follows the same pattern.

OCaml Approach

let subsets lst =
  let n = List.length lst in
  let arr = Array.of_list lst in
  List.init (1 lsl n) (fun mask ->
    List.init n (fun i ->
      if mask land (1 lsl i) <> 0 then [arr.(i)] else []
    ) |> List.concat
  )

Or with backtracking:

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

The recursive OCaml version is clean and idiomatic — divide into subsets with and without the head element.

Full Source

#![allow(clippy::all)]
// 1066: All Subsets (Power Set) — Backtracking vs Bitmasking

// Approach 1: Backtracking
fn subsets_backtrack(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    let mut current = Vec::new();

    fn build(start: usize, nums: &[i32], current: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
        results.push(current.clone());
        for i in start..nums.len() {
            current.push(nums[i]);
            build(i + 1, nums, current, results);
            current.pop();
        }
    }

    build(0, nums, &mut current, &mut results);
    results
}

// Approach 2: Bitmasking
fn subsets_bitmask(nums: &[i32]) -> Vec<Vec<i32>> {
    let n = nums.len();
    let total = 1 << n;
    (0..total)
        .map(|mask| {
            (0..n)
                .filter(|&i| mask & (1 << i) != 0)
                .map(|i| nums[i])
                .collect()
        })
        .collect()
}

// Approach 3: Iterative doubling (fold)
fn subsets_fold(nums: &[i32]) -> Vec<Vec<i32>> {
    nums.iter().fold(vec![vec![]], |acc, &x| {
        let mut result = acc.clone();
        for mut subset in acc {
            subset.push(x);
            result.push(subset);
        }
        result
    })
}

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

    #[test]
    fn test_backtrack() {
        let s = subsets_backtrack(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
        assert!(s.contains(&vec![]));
        assert!(s.contains(&vec![1, 2, 3]));
    }

    #[test]
    fn test_bitmask() {
        let s = subsets_bitmask(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
    }

    #[test]
    fn test_fold() {
        let s = subsets_fold(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
    }

    #[test]
    fn test_empty() {
        assert_eq!(subsets_backtrack(&[]).len(), 1);
    }
}

(* 1066: All Subsets (Power Set) — Backtracking vs Bitmasking *)

(* Approach 1: Backtracking *)
let subsets_backtrack nums =
  let n = Array.length nums in
  let results = ref [] in
  let current = ref [] in
  let rec build start =
    results := List.rev !current :: !results;
    for i = start to n - 1 do
      current := nums.(i) :: !current;
      build (i + 1);
      current := List.tl !current
    done
  in
  build 0;
  List.rev !results

(* Approach 2: Bitmasking *)
let subsets_bitmask nums =
  let n = Array.length nums in
  let total = 1 lsl n in
  List.init total (fun mask ->
    let subset = ref [] in
    for i = 0 to n - 1 do
      if mask land (1 lsl i) <> 0 then
        subset := nums.(i) :: !subset
    done;
    List.rev !subset
  )

(* Approach 3: Functional — iterative doubling *)
let subsets_fold nums =
  Array.fold_left (fun acc x ->
    acc @ List.map (fun subset -> subset @ [x]) acc
  ) [[]] nums

let () =
  let s1 = subsets_backtrack [|1; 2; 3|] in
  assert (List.length s1 = 8);
  assert (List.mem [] s1);
  assert (List.mem [1; 2; 3] s1);

  let s2 = subsets_bitmask [|1; 2; 3|] in
  assert (List.length s2 = 8);

  let s3 = subsets_fold [|1; 2; 3|] in
  assert (List.length s3 = 8);

  assert (List.length (subsets_backtrack [||]) = 1);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_backtrack() {
        let s = subsets_backtrack(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
        assert!(s.contains(&vec![]));
        assert!(s.contains(&vec![1, 2, 3]));
    }

    #[test]
    fn test_bitmask() {
        let s = subsets_bitmask(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
    }

    #[test]
    fn test_fold() {
        let s = subsets_fold(&[1, 2, 3]);
        assert_eq!(s.len(), 8);
    }

    #[test]
    fn test_empty() {
        assert_eq!(subsets_backtrack(&[]).len(), 1);
    }
}

Deep Comparison

All Subsets (Power Set) — Comparison

Core Insight

Three approaches: backtracking (include/skip decisions), bitmasking (enumerate 0..2^n), and iterative doubling (fold over elements, cloning all subsets with new element added). Each has different elegance-performance tradeoffs.

OCaml Approach

• Backtracking with ref list and prepend/tail

• Bitmask: List.init total + lsl/land bit ops

• Fold: Array.fold_left with list append @ — elegant but allocates

• List.rev needed for ordering in backtrack/bitmask

Rust Approach

• Backtracking: push/pop + clone()

• Bitmask: nested iterator chain .map + .filter + .collect() — very idiomatic

• Fold: iter().fold(vec![vec![]], ...) with clone and push

• 1 << n for power of 2

Comparison Table

Aspect	OCaml	Rust
Bitmask idiom	`mask land (1 lsl i)`	`mask & (1 << i)`
Iterator chain	`List.init` + loop	`(0..total).map(...).collect()`
Fold doubling	`Array.fold_left` + `@`	`.fold(vec![vec![]], ...)` + clone
Subset count	`1 lsl n`	`1 << n`
Cloning	`List.rev` (structural sharing)	`.clone()` (deep copy)

Exercises

Implement subsets_of_size(nums: &[i32], k: usize) -> Vec<Vec<i32>> that generates only subsets of exactly size k.

Write subsets_unique(nums: &mut [i32]) -> Vec<Vec<i32>> that handles duplicate elements by sorting and skipping duplicates at each level.

Implement a lazy subset generator fn subsets_iter(nums: &[i32]) -> impl Iterator<Item=Vec<i32>> using bitmask iteration.

Open Source Repos

functional-rust

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

Rust