Solve minimum rate and subset sum

1. Minimum rate to finish vaults within a deadline: You are given an array vaults of positive integers representing the amount in each vault along a row. Each hour, the robber can work on exactly one vault and steal up to k units from that vault during that hour; excess capacity cannot be transferred to other vaults. The time to finish a vault of size v at rate k is ceil(v/k) hours. Given vaults = [3, 6, 7, 11] and h = 8, compute the minimum integer rate k such that all vaults can be emptied within h hours. Describe an efficient algorithm and analyze its time and space complexity.
2. Subset equals target sum: Given the integer set {2, 5, 3, 11} and a target sum 10, determine whether some (or all) of the integers can be selected so that their sum equals the target. Return true/false and outline your approach and complexity.

Minimum Rate to Empty All Vaults

You are given an array vaults of positive integers representing the amount of money in each vault along a row, and an integer h (the number of hours available). Each hour, the robber can work on exactly one vault and steal up to k units from that vault during that hour; excess capacity within an hour cannot be transferred to another vault. The time to fully empty a vault of size v at rate k is ceil(v / k) hours.

Return the minimum integer rate k such that all vaults can be emptied within h hours.

Example: vaults = [3, 6, 7, 11], h = 8 -> answer is 4 (at k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8).

This is the classic 'Koko Eating Bananas' pattern: the hours-needed function is monotonically non-increasing in k, so binary search the smallest feasible rate.

Constraints

• 1 <= vaults.length <= 10^5
• 1 <= vaults[i] <= 10^9
• vaults.length <= h <= 10^9 (h is at least the number of vaults, so a feasible rate always exists)

Hints

1. The number of hours required is a monotonic function of the rate k: a larger k never increases the total hours. This monotonicity is exactly what enables binary search.
2. Search the integer rate over the range [1, max(vaults)]. For a candidate k, the total hours are sum(ceil(v/k)) over all vaults. Use ceil(v/k) = (v + k - 1) // k to avoid floating point.
3. Find the smallest k for which total hours <= h. The lower bound is 1 (at least 1 unit/hour) and the upper bound is max(vaults) (one vault per hour is always feasible since h >= number of vaults).

Subset Equals Target Sum

Given an array of integers nums and an integer target, determine whether some subset of the elements (possibly empty, possibly all) can be selected so that their sum equals target. Each element may be used at most once. Return true if such a subset exists, otherwise false.

Example: nums = [2, 5, 3, 11], target = 10 -> true (2 + 3 + 5 = 10).

This is the classic Subset Sum decision problem, solvable with dynamic programming over reachable sums. The inputs here are non-negative; the empty subset sums to 0, so target = 0 is always reachable.

Constraints

• 0 <= nums.length <= 200
• 1 <= nums[i] <= 1000 (non-negative integers)
• 0 <= target <= 200000
• The empty subset is allowed, so target = 0 is always achievable.

Hints

1. Frame it as a reachability problem: track the set of sums you can form using a prefix of the elements. Start with {0} (the empty subset).
2. For each new number n, every previously reachable sum s gives a new reachable sum s + n. Discard sums that exceed target, since the values are non-negative and can never come back down.
3. The standard formulation is a boolean DP array dp[0..target] where dp[j] means sum j is reachable; iterate j downward when updating in place to ensure each element is used at most once. Return dp[target].