Split Sum Closest Problem

Split Sum Closest Problem — ExecCode Hard DSA Practice

Solve the Split Sum Closest problem on ExecCode. Free online hard DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Choose any subset of nums (possibly empty) whose sum is as close as possible to target. n around 40 is too big for 2^n, so you split the array in half, enumerate 2^{n/2} sums on each side, and binary-search the partner half. Return the subset sum closest to target. If two sums are equally close, return the smaller sum. You are given: nums — integers, may be negative target — goal Return closest subset sum. You do not have to use every element.

Examples

Input {'nums': [1, 3, 5], 'target': 7}; Output 6. Input {'nums': [10], 'target': 1}; Output 0. Input {'nums': [2, 2], 'target': 4}; Output 4

Constraints

Empty subset sum is 0 All-or-nothing both allowed

Practice Split Sum Closest free on ExecCode. Browse DSA problems, topic map, and placement guides.