#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/complete-search/meet-in-the-middle-example

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/complete-search/meet-in-the-middle-example

Repovive

Meet in the Middle - Example - Complete Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Meet in the Middle - Example

4Sum II problem.

Problem: Find if any subset of $40$ numbers sums to target.

$1.$ Split into two halves of $20$ .

$2.$ Generate all $2^{20}$ sums for each half.

$3.$ Sort second half. For each sum $s$ in first half, binary search for $target - s$ .

for s in firstHalfSums:
    if binarySearch(secondHalfSums, target - s):
        return true

Time: $O(2^{n/2} \cdot n)$ instead of $O(2^n)$ . For $n=40$ : $10^7$ vs $10^{12}$ .