Meet in the Middle

Nasıl düşünülür

Meet in the middle, 2^n çok büyük ama 2^(n/2) değilken alt küme sayımlandırmayı kurtaran hiledir. Diziyi ikiye böl. Sol yarının tüm 2^(n/2) alt kümelerini say, toplamlarını (veya herhangi bir agregatı) sıralı bir listede veya hash map’te sakla. Sonra sağ yarının tüm 2^(n/2) alt kümelerini say; her biri için ihtiyaç duyduğun tamamlayıcıyı hesapla ve solda ara. Anahtar: 2 * 2^(n/2), 2^n’den çok daha küçük, n=40’ta 2^40 trilyon ama 2 * 2^20 iki milyon.

Birleştirme adımı sorguya bağlı: “hedefe en yakın toplam” için sol toplamları sırala, her sağ alt kümenin tamamlayıcısını ikili ara. “Hedefe uyan alt küme say” için sol toplamlarını sayılarla hash map kullan. “Kısıtlı partisyon” için sağ sayımı soldan filtrele.

Şablon şekilleri

Şekil	Temel hamle	Örnek
En yakın toplam	Sol sıralı; sağ alt küme başına tamamlayıcı ikili ara	LC 1755, LC 2035
Alt küme sayma	Sol hash map; sağ alt küme başına say	LC 1655
Min fark partisyon	İki yarı; sol sırala; sağ başına en iyi solu bul	LC 2035
Kısıt doyurma	Yarı başına durum kodla; join anahtarında eşle	LC 1601

Karmaşıklık temeli

Her yarıyı sayma: O(2^(n/2) * n/2). Sıralama + sorgu: O(2^(n/2) * log(2^(n/2))). Toplam: O(n * 2^(n/2)) zaman, O(2^(n/2)) alan. n=40’ta yaklaşık 2 * 10^7, uygulanabilir.

Şablondan probleme

1. n’in ~30-45 tatlı noktasında olduğunu doğrula, daha küçükse brute force, daha büyükse başka teknik gerek.
2. Girdiyi kabaca eşit iki yarıya böl.
3. Her yarının tüm alt kümelerini say, ilgili agregatı sakla.
4. Bir yarıyı sırala veya hash’le; diğer yarının her alt kümesi için tamamlayıcıyı ara.
5. Çift sayıma dikkat: bir yanda boş + diğer yanda boş = boş küme, probleme göre say veya hariç tut.

/** Meet in the middle template: closest subset sum to target. */

export function closestSubsetSum(nums: number[], target: number): number {
  const n = nums.length;
  const mid = Math.floor(n / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const leftSums = new Set<number>([0]);
  for (const v of left) {
    for (const s of [...leftSums]) leftSums.add(s + v);
  }
  const sorted = [...leftSums].sort((a, b) => a - b);

  let best = 0;
  const rightSums = [0];
  for (const v of right) {
    for (const s of [...rightSums]) rightSums.push(s + v);
  }
  for (const r of rightSums) {
    const need = target - r;
    let lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
      const m = (lo + hi + 1) >> 1;
      if (sorted[m]! <= need) lo = m;
      else hi = m - 1;
    }
    if (Math.abs(r + sorted[lo]! - target) < Math.abs(best - target)) {
      best = r + sorted[lo]!;
    }
  }
  return best;
}

/** Meet in the middle template: closest subset sum to target. */

export function closestSubsetSum(nums: number[], target: number): number {
  const n = nums.length;
  const mid = Math.floor(n / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  const leftSums = new Set<number>([0]);
  for (const v of left) {
    for (const s of [...leftSums]) leftSums.add(s + v);
  }
  const sorted = [...leftSums].sort((a, b) => a - b);

  let best = 0;
  const rightSums = [0];
  for (const v of right) {
    for (const s of [...rightSums]) rightSums.push(s + v);
  }
  for (const r of rightSums) {
    const need = target - r;
    let lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
      const m = (lo + hi + 1) >> 1;
      if (sorted[m]! <= need) lo = m;
      else hi = m - 1;
    }
    if (Math.abs(r + sorted[lo]! - target) < Math.abs(best - target)) {
      best = r + sorted[lo]!;
    }
  }
  return best;
}