The smallest difference between two groups

def min_difference(nums):
    total = sum(nums)
    half = total // 2
    reach = [True] + [False] * half
    for x in nums:
        for t in range(half, x - 1, -1):     # 0/1: downwards
            reach[t] = reach[t] or reach[t - x]
    s = max(t for t in range(half + 1) if reach[t])   # the group closest to half
    return total - 2 * s

#include <numeric>
#include <vector>

int solve(const std::vector<int>& nums) {
    int total = std::accumulate(nums.begin(), nums.end(), 0), half = total / 2;
    std::vector<bool> reach(half + 1, false);
    reach[0] = true;
    for (int x : nums)
        for (int t = half; t >= x; --t) reach[t] = reach[t] || reach[t - x];
    int s = half;
    while (!reach[s]) --s;                         // the reachable sum closest to half
    return total - 2 * s;
}

class Solution {
    public int minDifference(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        int half = total / 2;
        boolean[] reach = new boolean[half + 1];
        reach[0] = true;
        for (int x : nums)
            for (int t = half; t >= x; t--) reach[t] = reach[t] || reach[t - x];
        int s = half;
        while (!reach[s]) s--;                     // the reachable sum closest to half
        return total - 2 * s;
    }
}

function minDifference(nums) {
  const total = nums.reduce((a, b) => a + b, 0), half = Math.floor(total / 2);
  const reach = [true, ...new Array(half).fill(false)];
  for (const x of nums) for (let t = half; t >= x; t--) reach[t] = reach[t] || reach[t - x];
  return total - 2 * reach.lastIndexOf(true);      // the reachable sum closest to half
}

fn solve(nums: &[i64]) -> i64 {
    let total: i64 = nums.iter().sum();
    let half = (total / 2) as usize;
    let mut reach = vec![false; half + 1];
    reach[0] = true;
    for &x in nums {
        let x = x as usize;
        if x > half {
            continue;
        }
        for t in (x..=half).rev() {
            reach[t] = reach[t] || reach[t - x];
        }
    }
    let s = (0..=half).rev().find(|&t| reach[t]).unwrap() as i64;   // closest to half
    total - 2 * s
}

import qualified Data.Set as S

solve :: [Int] -> Int
solve nums = total - 2 * S.findMax (foldl add (S.singleton 0) nums)   -- the reachable sum closest to half
  where
    total = sum nums
    half = total `div` 2
    add reach x = S.union reach (S.fromList [t + x | t <- S.toList reach, t + x <= half])