The problem
Choose some of the numbers in the list a (any of them, or none). Return how close their sum can get to target: the smallest possible value of abs(sum - target). The empty choice has sum 0.
closest_sum([3, 9, 14], 20) # 3: 17 or 23
closest_sum([3, 9, 14], 23) # 0: 9 + 14
closest_sum([-7, 4, 10], 2) # 1: -7 + 10 = 3
closest_sum([], 5) # 5
Limits
ahas up to 36 numbers, each from −10¹² to 10¹² (minus and plus a million million).targetis a whole number of the same size or larger.- 36 numbers have 2³⁶, about 69 billion, subsets: listing them all is far too slow. The biggest tests have 5 seconds each.
Builds on BITS-5 Subsets as bitmasks.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
13 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | An exact hit | Not run | |
| 3 | No items | Not run | |
| 4 | Target 0 | Not run | |
| 5 | Negative values | Not run | |
| 6 | One item | Not run | |
| 7 | Equal items | Not run | |
| 8 | 16 small values | Not run | |
| 9 | 20 large values | Not run | |
| 10 | 30 values | Not run | |
| 11 | 35 values | Not run | |
| 12 | 36 values | Not run | |
| 13 | Far above every sum | Not run |