The O(n) Club: All Possible Parentheses — Recursion Goes Wild

The O(n) Club: All Possible Parentheses — Recursion Goes Wild

⚡ TL;DR

Given an expression like “2*3-4*5”, your job is to group numbers using parentheses every conceivable way, then return all results. Think: giving a spreadsheet every possible bracket combo and asking, ‘Which sum breaks first?’ Naive recursion works but is slower than loading Eclipse with 50 plugins. Witness Java in the wild:

// Brute-force. Only for the brave (or desperate):
public List<Integer> diffWaysToCompute(String input) {
  List<Integer> out = new ArrayList<>();
  for (int i = 0; i < input.length(); i++) {
    char c = input.charAt(i);
    if (c == '+' || c == '-' || c == '*') {
      List<Integer> left = diffWaysToCompute(input.substring(0, i));
      List<Integer> right = diffWaysToCompute(input.substring(i+1));
      for (int l : left) for (int r : right)
        out.add(c == '+' ? l+r : c == '-' ? l-r : l*r);
    }
  }
  if (out.isEmpty()) out.add(Integer.parseInt(input));
  return out;
}

🧠 How Devs Usually Mess This Up

#1 – Doing everything left-to-right: This isn’t school math. Every operator screams: “Split me!” Process all of them. If you go left-to-right only, you get one answer. The interviewer gets a new favorite candidate—anyone but you.

#2 – Forgetting the base case: When the string is just digits (like “12”), return it as a single result, or Java’s going to treat your recursion like infinite monkeys on typewriters.

#3 – No memoization: Welcome to O(2^N) recursive doomsday. Enjoy your frying laptop. Cache, cache, cache!

🔍 What’s Actually Going On

Picture this problem as an office whiteboard, where each operator (+, -, *) is a possible way to split your equation. For every split, recursively solve left and right, mix the results every way you can—then repeat, forever. It’s like evaluating a circuit with every possible wiring, or running a “what if” on every spreadsheet scenario.
Memoization is your friend: store results for any repeated sub-expression. Otherwise, you’re just running in circles, like a mutex waiting for a rogue thread.

🛠️ PseudoCode

• If input only has digits:

  if (input is just a number)
    return [number]

  And breathe. This is your recursion anchor.

• For each character in input:

  for (char c : input)
    if c is +, - or *
      left = compute(left half)
      right = compute(right half)

  Every operator is a party invitation for parentheses.

• Combine all combos:

  for (l : left)
    for (r : right)
      result.add(apply(l, r, operator))

  Double loops, double the fun. (Not really.)

• Memoize:

  memo[input] = result

  Otherwise, say goodbye to runtime as you know it.

💻 The Code

import java.util.*;
public class Solution {
    private Map<String, List<Integer>> memo = new HashMap<>();
    public List<Integer> diffWaysToCompute(String input) {
        if (memo.containsKey(input)) return memo.get(input);
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i+1));
                for (int l : left)
                    for (int r : right)
                        out.add(c == '+' ? l+r : c == '-' ? l-r : l*r);
            }
        }
        if (out.isEmpty()) out.add(Integer.parseInt(input));
        memo.put(input, out);
        return out;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Skipping the base case: Infinite recursion: not as fun as it sounds.
• Ignoring multi-digit numbers: ‘12’ isn’t ‘1’ then ‘2’. Don’t rewrite history—parse responsibly.
• No memo? Bad times: Without caching, the only thing you’ll produce is regret.
• Duplicates happen: Different splits may yield the same output—no need to dedupe, that’s not the goal here.
• Complexity check: Memoized: O(N * 2^N) time-ish. Not memoized: O(wait until next interview).

🧠 Interviewer Brain-Tattoo

“Every operator’s a branching path in the recursion amusement park—visit them all, but don’t forget to stamp your ticket (memoization) before reriding!”