Closest subsequence sum

Array Two Pointers Dynamic Programming Bit Manipulation Sorting Bitmask

43.2% acceptance

Feb 25, 2026

1004

You are given an integer array nums and an integer goal. You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence's elements is sum, then you want to minimize the absolute difference abs(sum - goal). Return the minimum possible value of abs(sum - goal).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_abs_difference(nums: Vec<i32>, goal: i32) -> i32 {
    let n = nums.len();
    let half = n / 2;
    // Generate all subset sums for first half
    let sums1 = Self::subset_sums(&nums[..half]);
    // Generate all subset sums for second half
    let mut sums2 = Self::subset_sums(&nums[half..]);
    sums2.sort_unstable();

    let mut ans = i32::MAX;
    let goal = goal as i64;
    for &s1 in &sums1 {
      let need = goal - s1;
      // Binary search in sums2 for closest to need
      let pos = sums2.partition_point(|&x| x < need);
      if pos < sums2.len() {
        ans = ans.min((s1 + sums2[pos] - goal).abs() as i32);
      }
      if pos > 0 {
        ans = ans.min((s1 + sums2[pos - 1] - goal).abs() as i32);
      }
    }
    ans
  }

  fn subset_sums(nums: &[i32]) -> Vec<i64> {
    let mut sums = vec![0i64];
    for &n in nums {
      let len = sums.len();
      for i in 0..len {
        sums.push(sums[i] + n as i64);
      }
    }
    sums
  }
}