Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Partition Array Into Two Arrays to Minimize Sum Difference

Problem (yeniden ifade)

nums uzunluğu 2n (n ≤ 15). İki n uzunluklu diziye böl. |sum(birinci) − sum(ikinci)| değerini küçült.

Sezgi

|sum1 − sum2| = |2·sum1 − total| ve sum1 tam n eleman kullanmalı. C(2n, n) ağır; her yarı n ≤ 15, tüm alt kümeleri boyuta göre grupla.

Yaklaşımlar

Ortada buluş, boyuta göre toplamlar

Doğrulanmadı

Zaman O(n·2^n)Alan O(2^n)

Fikir. İki n elemanlı yarıya böl. Her alt küme toplamını kardinalite k kovasına koy. Sol k için sağ n−k içinde total/2 − leftSum’a en yakını ikili ara (taban indeks ve lo+1). Negatifler sorun değil; kovalar sıralı.

Yürüyüş. [3,9,7,3]: yarılar [3,9] ve [7,3]. Boyut-1 eşleşme 3+7=10, toplam 22 → fark 2. [-36,36] sıfıra bölünemez: her taraf bir eleman almalı → 72.

Trade-off. Alt küme-toplamı DP yetmez: değerler ±1e7 ve tam n kısıtı var. MITM bu ölçek için.

Çözüm

export function minimumDifference(nums: number[]): number {
  const n = nums.length >> 1;
  const left = nums.slice(0, n);
  const right = nums.slice(n);
  const total = nums.reduce((a, b) => a + b, 0);

  const sumsBySize = (arr: number[]): number[][] => {
    const m = arr.length;
    const buckets: number[][] = Array.from({ length: m + 1 }, () => []);
    for (let mask = 0; mask < 1 << m; mask++) {
      let s = 0, k = 0;
      for (let i = 0; i < m; i++) {
        if (mask & (1 << i)) {
          s += arr[i]!;
          k++;
        }
      }
      buckets[k]!.push(s);
    }
    for (const b of buckets) b.sort((a, b) => a - b);
    return buckets;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const L = sumsBySize(left);
  const R = sumsBySize(right);
  let ans = Number.MAX_SAFE_INTEGER;
  for (let k = 0; k <= n; k++) {
    const rightSums = R[n - k]!;
    for (const ls of L[k]!) {
      const rs = closest(rightSums, (total - 2 * ls) >> 1);
      const diff = Math.abs(2 * (ls + rs) - total);
      if (diff < ans) ans = diff;
    }
  }
  return ans;
}

export function minimumDifference(nums: number[]): number {
  const n = nums.length >> 1;
  const left = nums.slice(0, n);
  const right = nums.slice(n);
  const total = nums.reduce((a, b) => a + b, 0);

  const sumsBySize = (arr: number[]): number[][] => {
    const m = arr.length;
    const buckets: number[][] = Array.from({ length: m + 1 }, () => []);
    for (let mask = 0; mask < 1 << m; mask++) {
      let s = 0, k = 0;
      for (let i = 0; i < m; i++) {
        if (mask & (1 << i)) {
          s += arr[i]!;
          k++;
        }
      }
      buckets[k]!.push(s);
    }
    for (const b of buckets) b.sort((a, b) => a - b);
    return buckets;
  };

  const closest = (a: number[], need: number): number => {
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (a[mid]! <= need) lo = mid;
      else hi = mid - 1;
    }
    let best = a[lo]!;
    if (lo + 1 < a.length && Math.abs(a[lo + 1]! - need) < Math.abs(best - need)) {
      best = a[lo + 1]!;
    }
    return best;
  };

  const L = sumsBySize(left);
  const R = sumsBySize(right);
  let ans = Number.MAX_SAFE_INTEGER;
  for (let k = 0; k <= n; k++) {
    const rightSums = R[n - k]!;
    for (const ls of L[k]!) {
      const rs = closest(rightSums, (total - 2 * ls) >> 1);
      const diff = Math.abs(2 * (ls + rs) - total);
      if (diff < ans) ans = diff;
    }
  }
  return ans;
}

Şablon bağlantısı

En-yakın-toplam MITM artı kardinalite birleşimi: sol boyut k ile sağ boyut n−k. Boş-karşı-dolu yasadışı — cevabı |total| değil ∞ ile başlat.

Yansıma

İki yarı n eleman. Alt küme toplamlarını boyuta göre kovala. Sol k için sağ n−k içinde total/2 − sola en yakını ara.
İki parçanın boyu eşit. Fark |toplam − 2*alt|. Boş ve tam seçim farkı toplamdır.
Negatifler kovayı bozmaz, kovalar sıralı. Her yarı 2^n. Dizi boyu çift.