795 Advanced

795-subset-sum-dp — Subset Sum

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "795-subset-sum-dp — Subset Sum" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Subset sum asks: can a subset of given numbers sum to a target value? Key difference from OCaml: 1. **Right

Tutorial

The Problem

Subset sum asks: can a subset of given numbers sum to a target value? It is NP-complete in general but solvable in pseudo-polynomial O(n × target) time via DP. It underlies the 0/1 knapsack problem, is used in cryptography (merkle-hellman knapsack), and appears in scheduling (can a set of tasks exactly fill a time slot?) and partitioning problems (can employees be split into equal-salary teams?).

🎯 Learning Outcomes

• Model subset sum as dp[w] = whether sum w is achievable

• Apply the 0/1 knapsack recurrence with boolean values: dp[i] = dp[i] || dp[i - num]

• Iterate right-to-left to prevent using the same number twice

• Implement count_subsets(nums, target) for counting the number of valid subsets

• Understand the connection to the partition problem (target = sum/2)

Code Example

#![allow(clippy::all)]
//! # Subset Sum

pub fn subset_sum(nums: &[i32], target: i32) -> bool {
    if target < 0 {
        return false;
    }
    let t = target as usize;
    let mut dp = vec![false; t + 1];
    dp[0] = true;
    for &n in nums {
        if n < 0 {
            continue;
        }
        let n = n as usize;
        for i in (n..=t).rev() {
            dp[i] = dp[i] || dp[i - n];
        }
    }
    dp[t]
}

pub fn count_subsets(nums: &[usize], target: usize) -> usize {
    let mut dp = vec![0usize; target + 1];
    dp[0] = 1;
    for &n in nums {
        for i in (n..=target).rev() {
            dp[i] += dp[i - n];
        }
    }
    dp[target]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_subset() {
        assert!(subset_sum(&[3, 34, 4, 12, 5, 2], 9));
    }
    #[test]
    fn test_count() {
        assert_eq!(count_subsets(&[1, 2, 3], 4), 1);
    }
}

(* Subset Sum — boolean DP, O(n×T), plus all-subsets reconstruction *)

let subset_sum nums target =
  (* dp.(s) = true if sum s is achievable *)
  let dp = Array.make (target + 1) false in
  dp.(0) <- true;
  List.iter (fun x ->
    (* Iterate in reverse to avoid using x twice (0/1 knapsack) *)
    for s = target downto x do
      if dp.(s - x) then dp.(s) <- true
    done
  ) nums;
  dp.(target)

(* Find the actual subset *)
let subset_find nums target =
  let n      = List.length nums in
  let arr    = Array.of_list nums in
  let dp     = Array.make_matrix (n + 1) (target + 1) false in
  dp.(0).(0) <- true;
  for i = 1 to n do
    let x = arr.(i - 1) in
    for s = 0 to target do
      dp.(i).(s) <- dp.(i-1).(s) || (s >= x && dp.(i-1).(s-x))
    done
  done;
  if not dp.(n).(target) then None
  else begin
    let subset = ref [] in
    let s = ref target in
    for i = n downto 1 do
      if not dp.(i-1).(!s) then begin
        subset := arr.(i-1) :: !subset;
        s      := !s - arr.(i-1)
      end
    done;
    Some !subset
  end

let () =
  let nums   = [3; 34; 4; 12; 5; 2] in
  let target = 9 in
  Printf.printf "nums=%s target=%d\n"
    ("[" ^ String.concat ";" (List.map string_of_int nums) ^ "]") target;
  Printf.printf "Has subset summing to %d: %b\n" target (subset_sum nums target);
  (match subset_find nums target with
   | None   -> Printf.printf "Subset: none\n"
   | Some s -> Printf.printf "Subset: [%s]\n"
       (String.concat "; " (List.map string_of_int s)));
  Printf.printf "Has subset summing to 30: %b\n" (subset_sum nums 30)

Key Differences

Right-to-left: Both languages use the same right-to-left trick to avoid counting elements twice; the direction is critical and easy to get wrong.

Boolean vs count: The same code structure works for both variants by changing the array type and operation (OR vs add).

NP-completeness: Both languages can only solve small instances efficiently; for large targets, the pseudo-polynomial O(n × target) becomes infeasible.

Cryptographic connection: The merkle-hellman knapsack cryptosystem (broken by Shamir) is based on subset sum; Rust is used in modern post-quantum cryptography research.

OCaml Approach

OCaml implements with Array.make (t+1) false. The right-to-left iteration: for i = t downto n do dp.(i) <- dp.(i) || dp.(i-n) done. The counting variant uses int array. OCaml's Array.blit can copy and shift for the "extend with reversed order" optimization. The partition problem variant: subset_sum nums (sum/2) where sum = List.fold_left (+) 0 nums.

Full Source

#![allow(clippy::all)]
//! # Subset Sum

pub fn subset_sum(nums: &[i32], target: i32) -> bool {
    if target < 0 {
        return false;
    }
    let t = target as usize;
    let mut dp = vec![false; t + 1];
    dp[0] = true;
    for &n in nums {
        if n < 0 {
            continue;
        }
        let n = n as usize;
        for i in (n..=t).rev() {
            dp[i] = dp[i] || dp[i - n];
        }
    }
    dp[t]
}

pub fn count_subsets(nums: &[usize], target: usize) -> usize {
    let mut dp = vec![0usize; target + 1];
    dp[0] = 1;
    for &n in nums {
        for i in (n..=target).rev() {
            dp[i] += dp[i - n];
        }
    }
    dp[target]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_subset() {
        assert!(subset_sum(&[3, 34, 4, 12, 5, 2], 9));
    }
    #[test]
    fn test_count() {
        assert_eq!(count_subsets(&[1, 2, 3], 4), 1);
    }
}

(* Subset Sum — boolean DP, O(n×T), plus all-subsets reconstruction *)

let subset_sum nums target =
  (* dp.(s) = true if sum s is achievable *)
  let dp = Array.make (target + 1) false in
  dp.(0) <- true;
  List.iter (fun x ->
    (* Iterate in reverse to avoid using x twice (0/1 knapsack) *)
    for s = target downto x do
      if dp.(s - x) then dp.(s) <- true
    done
  ) nums;
  dp.(target)

(* Find the actual subset *)
let subset_find nums target =
  let n      = List.length nums in
  let arr    = Array.of_list nums in
  let dp     = Array.make_matrix (n + 1) (target + 1) false in
  dp.(0).(0) <- true;
  for i = 1 to n do
    let x = arr.(i - 1) in
    for s = 0 to target do
      dp.(i).(s) <- dp.(i-1).(s) || (s >= x && dp.(i-1).(s-x))
    done
  done;
  if not dp.(n).(target) then None
  else begin
    let subset = ref [] in
    let s = ref target in
    for i = n downto 1 do
      if not dp.(i-1).(!s) then begin
        subset := arr.(i-1) :: !subset;
        s      := !s - arr.(i-1)
      end
    done;
    Some !subset
  end

let () =
  let nums   = [3; 34; 4; 12; 5; 2] in
  let target = 9 in
  Printf.printf "nums=%s target=%d\n"
    ("[" ^ String.concat ";" (List.map string_of_int nums) ^ "]") target;
  Printf.printf "Has subset summing to %d: %b\n" target (subset_sum nums target);
  (match subset_find nums target with
   | None   -> Printf.printf "Subset: none\n"
   | Some s -> Printf.printf "Subset: [%s]\n"
       (String.concat "; " (List.map string_of_int s)));
  Printf.printf "Has subset summing to 30: %b\n" (subset_sum nums 30)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_subset() {
        assert!(subset_sum(&[3, 34, 4, 12, 5, 2], 9));
    }
    #[test]
    fn test_count() {
        assert_eq!(count_subsets(&[1, 2, 3], 4), 1);
    }
}

Deep Comparison

OCaml vs Rust: Subset Sum Dp

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement partition_equal(nums: &[i32]) -> bool using subset sum: check if the total sum is even and if sum/2 is achievable.

Implement multi_subset_sum(nums, targets: &[i32]) -> Vec<bool> that answers multiple target queries in one pass using the same DP table.

Solve the exact partition into k subsets of equal sum using DFS with the subset sum DP as a feasibility oracle.

Open Source Repos

functional-rust

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

Rust