1060 Advanced

1060-partition-equal-subset — Partition Equal Subset Sum

Functional Programming

Tutorial

The Problem

Given a set of positive integers, can it be partitioned into two subsets with equal sums? This is an NP-complete problem in general, but the DP solution runs in O(n × sum/2) — pseudo-polynomial and practical for reasonable input sizes.

The problem is equivalent to: can a subset sum to exactly half of the total? Applications include load balancing (split tasks equally between two workers), scheduling (divide work evenly), and cryptographic range proofs.

🎯 Learning Outcomes

• Transform "can we partition into two equal subsets" into "can subset sum to target = sum/2"

• Implement boolean DP for subset sum

• Use a HashSet<i32> approach as an alternative

• Understand early termination when total is odd

• Connect to the NP-hardness of general partition problems

Code Example

#![allow(clippy::all)]
// 1060: Partition Equal Subset Sum — Boolean DP

use std::collections::{HashMap, HashSet};

// Approach 1: Bottom-up boolean DP
fn can_partition(nums: &[i32]) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = total as usize / 2;
    let mut dp = vec![false; target + 1];
    dp[0] = true;
    for &num in nums {
        let num = num as usize;
        for j in (num..=target).rev() {
            if dp[j - num] {
                dp[j] = true;
            }
        }
    }
    dp[target]
}

// Approach 2: Using HashSet for reachable sums
fn can_partition_set(nums: &[i32]) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = total / 2;
    let mut reachable = HashSet::new();
    reachable.insert(0i32);
    for &num in nums {
        let new_sums: Vec<i32> = reachable
            .iter()
            .map(|&s| s + num)
            .filter(|&s| s <= target)
            .collect();
        for s in new_sums {
            reachable.insert(s);
        }
        if reachable.contains(&target) {
            return true;
        }
    }
    reachable.contains(&target)
}

// Approach 3: Recursive with memoization
fn can_partition_memo(nums: &[i32]) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = total / 2;
    fn solve(
        i: usize,
        remaining: i32,
        nums: &[i32],
        cache: &mut HashMap<(usize, i32), bool>,
    ) -> bool {
        if remaining == 0 {
            return true;
        }
        if i >= nums.len() || remaining < 0 {
            return false;
        }
        if let Some(&v) = cache.get(&(i, remaining)) {
            return v;
        }
        let v =
            solve(i + 1, remaining - nums[i], nums, cache) || solve(i + 1, remaining, nums, cache);
        cache.insert((i, remaining), v);
        v
    }
    let mut cache = HashMap::new();
    solve(0, target, nums, &mut cache)
}

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

    #[test]
    fn test_can_partition() {
        assert!(can_partition(&[1, 5, 11, 5]));
        assert!(!can_partition(&[1, 2, 3, 5]));
        assert!(can_partition(&[1, 1]));
    }

    #[test]
    fn test_can_partition_set() {
        assert!(can_partition_set(&[1, 5, 11, 5]));
        assert!(!can_partition_set(&[1, 2, 3, 5]));
    }

    #[test]
    fn test_can_partition_memo() {
        assert!(can_partition_memo(&[1, 5, 11, 5]));
        assert!(!can_partition_memo(&[1, 2, 3, 5]));
    }
}

(* 1060: Partition Equal Subset Sum — Boolean DP *)

(* Approach 1: Bottom-up boolean DP *)
let can_partition nums =
  let total = Array.fold_left ( + ) 0 nums in
  if total mod 2 <> 0 then false
  else begin
    let target = total / 2 in
    let dp = Array.make (target + 1) false in
    dp.(0) <- true;
    Array.iter (fun num ->
      for j = target downto num do
        if dp.(j - num) then dp.(j) <- true
      done
    ) nums;
    dp.(target)
  end

(* Approach 2: Using a set for reachable sums *)
module IntSet = Set.Make(Int)

let can_partition_set nums =
  let total = Array.fold_left ( + ) 0 nums in
  if total mod 2 <> 0 then false
  else begin
    let target = total / 2 in
    let reachable = Array.fold_left (fun acc num ->
      IntSet.fold (fun s new_acc ->
        let sum = s + num in
        if sum <= target then IntSet.add sum new_acc else new_acc
      ) acc acc
    ) (IntSet.singleton 0) nums in
    IntSet.mem target reachable
  end

(* Approach 3: Recursive with memoization *)
let can_partition_memo nums =
  let total = Array.fold_left ( + ) 0 nums in
  if total mod 2 <> 0 then false
  else begin
    let target = total / 2 in
    let n = Array.length nums in
    let cache = Hashtbl.create 128 in
    let rec solve i remaining =
      if remaining = 0 then true
      else if i >= n || remaining < 0 then false
      else
        match Hashtbl.find_opt cache (i, remaining) with
        | Some v -> v
        | None ->
          let v = solve (i + 1) (remaining - nums.(i)) || solve (i + 1) remaining in
          Hashtbl.add cache (i, remaining) v;
          v
    in
    solve 0 target
  end

let () =
  assert (can_partition [|1; 5; 11; 5|] = true);
  assert (can_partition [|1; 2; 3; 5|] = false);
  assert (can_partition [|1; 1|] = true);
  assert (can_partition [|2; 2; 3; 5|] = false);

  assert (can_partition_set [|1; 5; 11; 5|] = true);
  assert (can_partition_set [|1; 2; 3; 5|] = false);

  assert (can_partition_memo [|1; 5; 11; 5|] = true);
  assert (can_partition_memo [|1; 2; 3; 5|] = false);

  Printf.printf "✓ All tests passed\n"

Key Differences

Boolean array: Both use bool arrays; Rust could use Vec<bool> (1 byte/element) or bit manipulation for memory efficiency.

HashSet approach: Rust's can_partition_set using HashSet is more readable but less space-efficient than the boolean array approach.

Early termination: Both check total % 2 != 0 first; Rust uses != and OCaml uses <> for not-equal.

NP-completeness: Both solve the NP-complete problem efficiently only because the target value is bounded; for arbitrary-precision integers, the problem becomes intractable.

OCaml Approach

let can_partition nums =
  let total = List.fold_left (+) 0 nums in
  if total mod 2 <> 0 then false
  else
    let target = total / 2 in
    let dp = Array.make (target + 1) false in
    dp.(0) <- true;
    List.iter (fun num ->
      for j = target downto num do
        if dp.(j - num) then dp.(j) <- true
      done
    ) nums;
    dp.(target)

Structurally identical to Rust. The downto for reverse iteration is the OCaml idiom.

Full Source

#![allow(clippy::all)]
// 1060: Partition Equal Subset Sum — Boolean DP

use std::collections::{HashMap, HashSet};

// Approach 1: Bottom-up boolean DP
fn can_partition(nums: &[i32]) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = total as usize / 2;
    let mut dp = vec![false; target + 1];
    dp[0] = true;
    for &num in nums {
        let num = num as usize;
        for j in (num..=target).rev() {
            if dp[j - num] {
                dp[j] = true;
            }
        }
    }
    dp[target]
}

// Approach 2: Using HashSet for reachable sums
fn can_partition_set(nums: &[i32]) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = total / 2;
    let mut reachable = HashSet::new();
    reachable.insert(0i32);
    for &num in nums {
        let new_sums: Vec<i32> = reachable
            .iter()
            .map(|&s| s + num)
            .filter(|&s| s <= target)
            .collect();
        for s in new_sums {
            reachable.insert(s);
        }
        if reachable.contains(&target) {
            return true;
        }
    }
    reachable.contains(&target)
}

// Approach 3: Recursive with memoization
fn can_partition_memo(nums: &[i32]) -> bool {
    let total: i32 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    let target = total / 2;
    fn solve(
        i: usize,
        remaining: i32,
        nums: &[i32],
        cache: &mut HashMap<(usize, i32), bool>,
    ) -> bool {
        if remaining == 0 {
            return true;
        }
        if i >= nums.len() || remaining < 0 {
            return false;
        }
        if let Some(&v) = cache.get(&(i, remaining)) {
            return v;
        }
        let v =
            solve(i + 1, remaining - nums[i], nums, cache) || solve(i + 1, remaining, nums, cache);
        cache.insert((i, remaining), v);
        v
    }
    let mut cache = HashMap::new();
    solve(0, target, nums, &mut cache)
}

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

    #[test]
    fn test_can_partition() {
        assert!(can_partition(&[1, 5, 11, 5]));
        assert!(!can_partition(&[1, 2, 3, 5]));
        assert!(can_partition(&[1, 1]));
    }

    #[test]
    fn test_can_partition_set() {
        assert!(can_partition_set(&[1, 5, 11, 5]));
        assert!(!can_partition_set(&[1, 2, 3, 5]));
    }

    #[test]
    fn test_can_partition_memo() {
        assert!(can_partition_memo(&[1, 5, 11, 5]));
        assert!(!can_partition_memo(&[1, 2, 3, 5]));
    }
}

(* 1060: Partition Equal Subset Sum — Boolean DP *)

(* Approach 1: Bottom-up boolean DP *)
let can_partition nums =
  let total = Array.fold_left ( + ) 0 nums in
  if total mod 2 <> 0 then false
  else begin
    let target = total / 2 in
    let dp = Array.make (target + 1) false in
    dp.(0) <- true;
    Array.iter (fun num ->
      for j = target downto num do
        if dp.(j - num) then dp.(j) <- true
      done
    ) nums;
    dp.(target)
  end

(* Approach 2: Using a set for reachable sums *)
module IntSet = Set.Make(Int)

let can_partition_set nums =
  let total = Array.fold_left ( + ) 0 nums in
  if total mod 2 <> 0 then false
  else begin
    let target = total / 2 in
    let reachable = Array.fold_left (fun acc num ->
      IntSet.fold (fun s new_acc ->
        let sum = s + num in
        if sum <= target then IntSet.add sum new_acc else new_acc
      ) acc acc
    ) (IntSet.singleton 0) nums in
    IntSet.mem target reachable
  end

(* Approach 3: Recursive with memoization *)
let can_partition_memo nums =
  let total = Array.fold_left ( + ) 0 nums in
  if total mod 2 <> 0 then false
  else begin
    let target = total / 2 in
    let n = Array.length nums in
    let cache = Hashtbl.create 128 in
    let rec solve i remaining =
      if remaining = 0 then true
      else if i >= n || remaining < 0 then false
      else
        match Hashtbl.find_opt cache (i, remaining) with
        | Some v -> v
        | None ->
          let v = solve (i + 1) (remaining - nums.(i)) || solve (i + 1) remaining in
          Hashtbl.add cache (i, remaining) v;
          v
    in
    solve 0 target
  end

let () =
  assert (can_partition [|1; 5; 11; 5|] = true);
  assert (can_partition [|1; 2; 3; 5|] = false);
  assert (can_partition [|1; 1|] = true);
  assert (can_partition [|2; 2; 3; 5|] = false);

  assert (can_partition_set [|1; 5; 11; 5|] = true);
  assert (can_partition_set [|1; 2; 3; 5|] = false);

  assert (can_partition_memo [|1; 5; 11; 5|] = true);
  assert (can_partition_memo [|1; 2; 3; 5|] = false);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_can_partition() {
        assert!(can_partition(&[1, 5, 11, 5]));
        assert!(!can_partition(&[1, 2, 3, 5]));
        assert!(can_partition(&[1, 1]));
    }

    #[test]
    fn test_can_partition_set() {
        assert!(can_partition_set(&[1, 5, 11, 5]));
        assert!(!can_partition_set(&[1, 2, 3, 5]));
    }

    #[test]
    fn test_can_partition_memo() {
        assert!(can_partition_memo(&[1, 5, 11, 5]));
        assert!(!can_partition_memo(&[1, 2, 3, 5]));
    }
}

Deep Comparison

Partition Equal Subset Sum — Comparison

Core Insight

This is a boolean variant of 0/1 knapsack: can we fill a "knapsack" of capacity total/2? The 1D boolean DP with reverse iteration is the standard approach. The HashSet variant trades space efficiency for conceptual clarity.

OCaml Approach

• IntSet module (functor-based ordered set) for reachable sums

• IntSet.fold to generate new sums — purely functional

• Boolean array with reverse for loop for standard DP

• Array.fold_left (+) 0 for sum

Rust Approach

• HashSet for reachable sums with collect/insert pattern

• Boolean vec! with reverse range (num..=target).rev()

• Early exit with contains(&target) check

• iter().sum() for total

Comparison Table

Aspect	OCaml	Rust
Set type	`Set.Make(Int)` (ordered, tree-based)	`HashSet<i32>` (hash-based)
Set iteration	`IntSet.fold`	`.iter().map().filter().collect()`
Boolean DP	`Array.make n false`	`vec![false; n]`
Sum	`Array.fold_left (+) 0`	`iter().sum()`
Early exit	Must check after fold	`if reachable.contains` mid-loop

Exercises

Extend to k_partition(nums: &[i32], k: usize) -> bool that checks if the array can be split into k equal-sum subsets.

Implement partition_count(nums: &[i32]) -> usize that counts the number of ways to partition into two equal-sum subsets.

Write min_subset_difference(nums: &[i32]) -> i32 that finds the partition minimizing the difference between the two subset sums (not necessarily equal).

Open Source Repos

functional-rust

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

Rust