Partition array into two arrays to minimize sum difference

Array Two Pointers Binary Search Dynamic Programming Bit Manipulation Sorting Ordered Set Bitmask

23.0% acceptance

Feb 25, 2026

3746

256

You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays. To partition nums, put each element of nums into one of the two arrays. Return the minimum possible absolute difference.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_difference(nums: Vec<i32>) -> i32 {
    let n = nums.len() / 2;
    let total: i64 = nums.iter().map(|&x| x as i64).sum();

    // For each count k, collect sums of all subsets of size k from the right half
    let mut right_sums: Vec<Vec<i64>> = vec![vec![]; n + 1];
    for mask in 0u32..(1 << n) {
      let mut sum = 0i64;
      let mut cnt = 0usize;
      for i in 0..n {
        if mask & (1 << i) != 0 {
          sum += nums[n + i] as i64;
          cnt += 1;
        }
      }
      right_sums[cnt].push(sum);
    }
    for v in right_sums.iter_mut() {
      v.sort_unstable();
    }

    let mut ans = i64::MAX;
    for mask in 0u32..(1 << n) {
      let mut left_sum = 0i64;
      let mut cnt = 0usize;
      for i in 0..n {
        if mask & (1 << i) != 0 {
          left_sum += nums[i] as i64;
          cnt += 1;
        }
      }
      let need_cnt = n - cnt;
      let target = total / 2 - left_sum;
      let v = &right_sums[need_cnt];
      let pos = v.partition_point(|&x| x < target);
      if pos < v.len() {
        let s1 = left_sum + v[pos];
        let s2 = total - s1;
        ans = ans.min((s1 - s2).abs());
      }
      if pos > 0 {
        let s1 = left_sum + v[pos - 1];
        let s2 = total - s1;
        ans = ans.min((s1 - s2).abs());
      }
    }
    ans as i32
  }
}