Introduction
Generating mountain ranges with upstrokes (/) and down-strokes (\) is a classic combinatorics problem equivalent to generating valid parentheses or Catalan number sequences. Given n pairs, the goal is to produce all strings of n upstrokes and n down-strokes where at no prefix do down-strokes exceed upstrokes (the "mountain" never goes below ground level). The number of valid mountain ranges of n pairs is the nth Catalan number. Backtracking recursion is the standard approach.
The Problem
For n = 3, the valid mountain ranges are:
1/\/\/\
2/\/\ /\
3/\ /\/\
4/\ /\/\
5/\/\ /\
Represented as strings: ///\\\, //\/\\, //\\/\, /\/\/\, /\//\\
Each string has exactly n forward slashes and n backslashes, and at every position, the count of / characters is greater than or equal to the count of \ characters.
Recursive Backtracking Solution
1import java.util.ArrayList;
2import java.util.List;
3
4public class MountainRanges {
5
6 public static List<String> generateMountains(int n) {
7 List<String> results = new ArrayList<>();
8 backtrack(results, new StringBuilder(), 0, 0, n);
9 return results;
10 }
11
12 private static void backtrack(List<String> results, StringBuilder current,
13 int up, int down, int n) {
14 if (current.length() == 2 * n) {
15 results.add(current.toString());
16 return;
17 }
18
19 // Can always go up if we haven't used all upstrokes
20 if (up < n) {
21 current.append('/');
22 backtrack(results, current, up + 1, down, n);
23 current.deleteCharAt(current.length() - 1);
24 }
25
26 // Can go down only if it won't go below ground level
27 if (down < up) {
28 current.append('\\');
29 backtrack(results, current, up, down + 1, n);
30 current.deleteCharAt(current.length() - 1);
31 }
32 }
33
34 public static void main(String[] args) {
35 List<String> mountains = generateMountains(3);
36 for (String m : mountains) {
37 System.out.println(m);
38 }
39 // Output:
40 // ///\\\
41 // //\/\\
42 // //\\/\
43 // /\/\/\
44 // /\//\\
45 System.out.println("Total: " + mountains.size()); // 5 (Catalan number C3)
46 }
47}
The key constraint is down < up — you can only add a down-stroke if the current height (upstrokes minus down-strokes) is above zero.
Visual ASCII Rendering
1public class MountainRenderer {
2
3 public static String render(String mountain) {
4 int height = 0;
5 int maxHeight = 0;
6
7 // Find maximum height
8 for (char c : mountain.toCharArray()) {
9 height += (c == '/') ? 1 : -1;
10 maxHeight = Math.max(maxHeight, height);
11 }
12
13 // Build the 2D grid
14 char[][] grid = new char[maxHeight][mountain.length()];
15 for (char[] row : grid) {
16 java.util.Arrays.fill(row, ' ');
17 }
18
19 height = 0;
20 for (int col = 0; col < mountain.length(); col++) {
21 if (mountain.charAt(col) == '/') {
22 grid[maxHeight - height - 1][col] = '/';
23 height++;
24 } else {
25 height--;
26 grid[maxHeight - height - 1][col] = '\\';
27 }
28 }
29
30 // Convert to string
31 StringBuilder sb = new StringBuilder();
32 for (char[] row : grid) {
33 sb.append(new String(row)).append('\n');
34 }
35 return sb.toString();
36 }
37
38 public static void main(String[] args) {
39 System.out.println(render("///\\\\\\"));
40 // /\
41 // / \
42 // / \
43
44 System.out.println(render("/\\/\\/\\"));
45 // /\/\/\
46 }
47}
Iterative Approach with Stack
1import java.util.*;
2
3public class MountainRangesIterative {
4
5 public static List<String> generateMountains(int n) {
6 List<String> results = new ArrayList<>();
7 // State: (current string, upstrokes used, downstrokes used)
8 Deque<int[]> stack = new ArrayDeque<>();
9 List<StringBuilder> builders = new ArrayList<>();
10
11 stack.push(new int[]{0, 0});
12 builders.add(new StringBuilder());
13
14 while (!stack.isEmpty()) {
15 int[] state = stack.pop();
16 StringBuilder sb = builders.remove(builders.size() - 1);
17 int up = state[0], down = state[1];
18
19 if (sb.length() == 2 * n) {
20 results.add(sb.toString());
21 continue;
22 }
23
24 if (down < up) {
25 StringBuilder downSb = new StringBuilder(sb).append('\\');
26 stack.push(new int[]{up, down + 1});
27 builders.add(downSb);
28 }
29
30 if (up < n) {
31 StringBuilder upSb = new StringBuilder(sb).append('/');
32 stack.push(new int[]{up + 1, down});
33 builders.add(upSb);
34 }
35 }
36
37 return results;
38 }
39}
The iterative version replaces recursion with an explicit stack, avoiding StackOverflowError for large n.
Counting with Catalan Numbers
1public class CatalanNumber {
2
3 // The number of valid mountain ranges of n pairs
4 public static long catalan(int n) {
5 if (n <= 1) return 1;
6
7 long[] dp = new long[n + 1];
8 dp[0] = 1;
9 dp[1] = 1;
10
11 for (int i = 2; i <= n; i++) {
12 for (int j = 0; j < i; j++) {
13 dp[i] += dp[j] * dp[i - 1 - j];
14 }
15 }
16 return dp[n];
17 }
18
19 public static void main(String[] args) {
20 for (int i = 0; i <= 10; i++) {
21 System.out.println("C(" + i + ") = " + catalan(i));
22 }
23 // C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42, ...
24 }
25}
The nth Catalan number C(n) = (2n)! / ((n+1)! * n!) gives the count without generating all sequences.
Common Pitfalls
Allowing down-strokes below ground level: The constraint is down < up, not down < n. Without this check, invalid sequences like \/ (going negative) are produced.
String concatenation in recursion: Creating new String objects at each recursive call is O(n) per call. Use StringBuilder with append/delete for O(1) per step.
Stack overflow for large n: Recursive solutions hit Java's default stack limit (~512-1024 frames) around n=500. Use the iterative approach or increase stack size with -Xss.
Confusing mountain ranges with balanced parentheses: They are mathematically identical — / maps to ( and \ maps to ). The same algorithm generates both.
Not escaping backslash in output: In Java strings, backslash must be escaped as \\. When printing mountain ranges, System.out.println("\\") outputs a single \.
Summary
Mountain ranges with / and \ are equivalent to balanced parentheses (Catalan numbers)
Use recursive backtracking with the constraint down < up to ensure validity
Use StringBuilder for efficient string building in recursion
The count of valid ranges for n pairs is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!)
Use iterative approach with explicit stack for large n to avoid stack overflow
ASCII rendering maps strokes to a 2D grid based on current height
