Show problems as
Classic problem #113MediumBacktrackingTreeDepth-First SearchBinary Tree

Path Sum II

Real-world version: Ridge Descents Matching a Drop
Tracked in this browser only
Read Path Sum II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstPath Sum & Root to Leaf · Binary Trees & BST, animated step by step

A survey of a mountain ridge records a network of marked waypoints. The topmost waypoint is the saddle, and every waypoint sends at most two marked forks further down the ridge, one bearing left and one bearing right. Each waypoint carries a signed height change in metres, positive where the ground rises onto it and negative where it falls onto it.

The survey arrives as waypoints, which lists the network one depth band at a time, left to right. Slot 0 holds the saddle. Each listed waypoint takes the next two unclaimed slots for its downhill forks, the left fork first and the right fork second. A slot holding null means no waypoint hangs there and it claims no slots of its own. Trailing null slots may be dropped from the end of the listing, and an empty listing means the survey found nothing.

A descent starts at the saddle, follows marked forks downhill, and stops at a waypoint with no fork leaving it. Its drop is the total of the height changes of every waypoint it touches, the saddle included.

Return every descent whose drop equals targetSum, each one given as the list of height changes in the order they are walked, from the saddle downward. The descents may come back in any order. Return an empty list when no descent matches.

Examples

Example 1

Input
waypoints = [6, 4, 9, 2, -1, null, 5], targetSum = 12
Output
[[6, 4, 2]]

The saddle records 6. Its left fork reaches 4, whose left fork holds 2, and that waypoint has nothing below it: 6 + 4 + 2 = 12. The survey's other two descents finish at -1 and at 5, dropping 9 and 20.

Example 2

Input
waypoints = [3, 5, null, -2, null, 4, null], targetSum = 10
Output
[[3, 5, -2, 4]]

The ridge runs straight down: 3, then 5, then -2, then 4. Only the last of those has no fork leaving it, and the four height changes total 10.

Example 3

Input
waypoints = [7], targetSum = 7
Output
[[7]]

The saddle has no fork, so the single descent touches only it and drops 7, which matches.

Example 4

Input
waypoints = [], targetSum = 0
Output
[]

The survey lists no waypoints at all, so there is no descent to report.

Example 5

Input
waypoints = [4, 1, 2, null, null, 6, -1], targetSum = 5
Output
[[4, 1], [4, 2, -1]]

The saddle's left fork holds 1 with nothing below it, and 4 + 1 = 5. Its right fork holds 2 and still has two forks of its own: the one holding -1 brings that descent back to 5, while the one holding 6 finishes at 12.

Constraints

  • The number of listed waypoints is in the range [0, 5000].
  • -1000 <= waypoints[i] <= 1000 for every non-null slot
  • -1000 <= targetSum <= 1000
  • waypoints[0] is not null unless the listing is empty
  • waypoints is a valid depth-band listing: every non-null slot after slot 0 was claimed as a fork by an earlier waypoint

The values you return may be in any order.

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.

Python
def path_sum(waypoints: list[int | None], targetSum: int) -> list[list[int]]:
Java
public List<List<Integer>> pathSum(Integer[] waypoints, int targetSum)

More on the same topics