Split into two equal halves

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    half = total // 2
    reach = [True] + [False] * half        # subset sums up to half
    for x in nums:
        for t in range(half, x - 1, -1):    # downwards: each number once
            reach[t] = reach[t] or reach[t - x]
    return reach[half]

#include <numeric>
#include <vector>

bool solve(const std::vector<int>& nums) {
    int total = std::accumulate(nums.begin(), nums.end(), 0);
    if (total % 2) return false;
    int 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];
    return reach[half];
}

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        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];
        return reach[half];
    }
}

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const half = total / 2, 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 reach[half];
}

fn solve(nums: &[i64]) -> bool {
    let total: i64 = nums.iter().sum();
    if total % 2 != 0 {
        return false;
    }
    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];
        }
    }
    reach[half]
}

import qualified Data.Set as S

solve :: [Int] -> Bool
solve nums = even total && S.member half (foldl add (S.singleton 0) nums)
  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])