Target Sum
Real-world version: Thruster Burn PlansThe statement here is our own: the same inputs, outputs and technique.
A station keeper has a queue of thruster burns already scheduled for the next pass. Burn i will move the station along its track by burns[i] units of drift, and before the pass starts the crew has to point each burn one way or the other: pointed ahead it adds that many units of drift, pointed astern it takes the same amount away. Every burn in the queue fires, in the order given, and none can be cancelled.
A plan is one choice of direction per burn. Two plans count as different as soon as a single burn points the other way, even when both plans finish on the same drift, and even when the burn measures 0 units and so pushes the station nowhere.
Return how many plans finish the pass with a drift of exactly net_shift units.
Examples
Example 1
- Input
- burns = [2, 2, 2, 2, 2], net_shift = 6
- Output
- 5
Four burns ahead and one astern land on 8 - 2 = 6, and any one of the five burns can be the one pointed astern, so there are five plans.
Example 2
- Input
- burns = [0, 5], net_shift = 5
- Output
- 2
The 5 must point ahead, while the 0 still has two directions to be recorded in, so both plans count.
Example 3
- Input
- burns = [3, 5], net_shift = -2
- Output
- 1
Only pointing the 3 ahead and the 5 astern reaches -2, so a single plan works.
Constraints
- 1 <= burns.length <= 20
- 0 <= burns[i] <= 1000
- 0 <= sum(burns) <= 1000
- -1000 <= net_shift <= 1000
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def burn_plan_count(burns: list[int], net_shift: int) -> int:public int burnPlanCount(int[] burns, int netShift)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's