Show problems as
Classic problem #22MediumStringDynamic ProgrammingBacktrackingBracket Sequences

Generate Parentheses

Real-world version: Ridge Walk Plans
Tracked in this browser only
Read Generate Parentheses on LeetCode(opens in a new tab)

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

Learn the pattern firstBacktracking · Recursion, animated step by step

A trail crew is drafting a loop hike along a ridge. The hike is a sequence of steps written as a string, where "U" gains one metre of height and "D" loses one metre.

A plan is valid when all three hold:

  • it uses exactly climbs up steps and exactly climbs down steps, so it is 2 * climbs steps long;
  • the hike ends back at the trailhead height;
  • after every single step the hiker is at or above the trailhead height, because the ridge drops away below that line.

Return every valid plan. The plans may be returned in any order.

Examples

Example 1

Input
climbs = 2
Output
["UUDD", "UDUD"]

Either both climbs are taken before either descent, or the hiker rises and drops twice in a row. Starting with a descent is ruled out by the third condition.

Example 2

Input
climbs = 4
Output
["UUUUDDDD", "UUUDUDDD", "UUUDDUDD", "UUUDDDUD", "UUDUUDDD", "UUDUDUDD", "UUDUDDUD", "UUDDUUDD", "UUDDUDUD", "UDUUUDDD", "UDUUDUDD", "UDUUDDUD", "UDUDUUDD", "UDUDUDUD"]

There are fourteen plans of eight steps that stay at or above the trailhead height and finish level with it.

Constraints

  • 1 <= climbs <= 8

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 ridge_walk_plans(climbs: int) -> list[str]:
Java
public List<String> ridgeWalkPlans(int climbs)

More on the same topics