1
impl Solution {
2
  pub fn minimum_difference(nums: Vec<i32>) -> i32 {
3
    let n = nums.len() / 2;
4
    let mut cache_left: Vec<Vec<i32>> = vec![vec![]; n + 1];
5
    let s: i32 = nums.iter().sum();
6
    for i in 0..(1 << n) as u32 {
7
      let len_left = i.count_ones() as usize;
8
      let sum_left = Solution::subsum(i, &nums[..n]);
9
      cache_left[len_left].push(s - 2 * sum_left);
10
    }
11

12
    cache_left.iter_mut().for_each(|x| x.sort_unstable());
13

14
    let mut min_absdiff = i32::max_value();
15
    for i in 0..(1 << n) as u32 {
16
      let sum_right = Solution::subsum(i, &nums[n..]);
17
      let cl = &cache_left[n - i.count_ones() as usize];
18
      let absdiff = Solution::bsearch_min_absdiff(cl, sum_right);
19
      min_absdiff = min_absdiff.min(absdiff);
20
    }
21
    min_absdiff
22
  }
23

24
  fn subsum(bitset: u32, nums: &[i32]) -> i32 {
25
    nums.iter().enumerate().fold(
26
      0,
27
      |sum, (j, v)| if bitset & (1 << j) != 0 { sum + v } else { sum },
28
    )
29
  }
30

31
  fn bsearch_min_absdiff(cl: &[i32], sum_right: i32) -> i32 {
32
    match cl.binary_search(&(2 * sum_right)) {
33
      Ok(_) => 0,
34
      Err(j) => {
35
        if j == 0 {
36
          (cl[j] - 2 * sum_right).abs()
37
        } else if j == cl.len() {
38
          (cl[j - 1] - 2 * sum_right).abs()
39
        } else {
40
          let absdiff_left = (cl[j - 1] - 2 * sum_right).abs();
41
          let absdiff_right = (cl[j] - 2 * sum_right).abs();
42
          absdiff_left.min(absdiff_right)
43
        }
44
      }
45
    }
46
  }
47
}