Standard Bar Dynamic Programming · DP on Subsequences O(n*k) · O(k)
A freight loader must prove that some combination of crates in a bay adds up to exactly the customs-declared weight k — no more, no less. Crates are indivisible, and not every declared weight is reachable. The audit bot scans all inclusion patterns and answers a single yes-or-no question for each manifest.
Input: An integer n, an array arr of n non-negative integers, and a target k.
Output: Return true when some subset of arr sums to exactly k, otherwise false.
1 <= n <= 2000 <= arr[i] <= 10^30 <= k <= 10^4Input: {"n":6,"arr":[3,34,4,12,5,2],"k":9}
Output: true
The subset 4 + 3 + 2 hits 9 exactly.
Input: {"n":3,"arr":[1,2,3],"k":4}
Output: true
1 + 3 = 4.