The O(n) Club: Expression Add Operators—The Recursion-Induced Headache Edition

The O(n) Club: Expression Add Operators—The Recursion-Induced Headache Edition

⚡ TL;DR

Take a string of digits. Insert ‘+’, ‘-‘, and ‘*’ between them (no reordering, no cheating) to build formulas that hit your target number. Welcome to backtracking’s angry cousin:

The brute force dream: try every possibility and pray Java’s Garbage Collector doesn’t ship you a ransom note.

This (very wrong) Java sample demonstrates what not to do:

// Doesn't handle precedence or leading zeros!
void dfs(String num, int idx, String path, int sum) {
    if (idx == num.length() && sum == target)
        res.add(path);
    for (int i = idx + 1; i <= num.length(); i++) {
        String left = num.substring(idx, i);
        int n = Integer.parseInt(left);
        dfs(num, i, path + '+' + n, sum + n);
        dfs(num, i, path + '-' + n, sum - n);
        dfs(num, i, path + '*' + n, sum * n); // lol, no precedence
    }
}

🧠 How Devs Usually Mess This Up

Believe it or not, your instinctive DFS is a booby trap. Here’s how people crash:

• Windows ’95 Calculator Syndrome: Operators everywhere, but absolutely no operator precedence. Multiplication does whatever it wants. Result? 2+3*2 is apparently 10 now. Nice.
• Leading Zeros—The Serial Offenders: Allowing operands like ’05’ sneak in. Only a single digit ‘0’ is allowed; anything else is basically asking for a NumberFormatException—spiritually and literally.
• Digit Isolation Disorder: Some folks only combine single digits (‘1+2+3′), forgetting that ’12+3’ is legal—and sometimes crucial. Don’t let your parser treat everyone as a loner.

🔍 What’s Actually Going On

Picture your algorithm wandering a decision tree forest. At every split between digits, it asks:
– Should I tack on another digit to my current number, or
– Should I throw down a ‘+’, ‘-‘, or ‘*’, start a new number, and recurse like a caffeinated squirrel?

Multiplication is the problem child—you have to keep track of the previous operand so that operator precedence doesn’t get trampled (i.e. adjust evaluated and prev). Each recursion step needs:
– The running total ( evaluated)
– The last operand (for multiplication)
– The current formula string ( path)

🛠️ PseudoCode

• Recursive function args: Position pos, current formula path, evaluated value, last operand ‘prev’.
• Base case: If all digits are used:
  • If evaluated == target, add path to results.
• For every possible split from pos to end of string:
  • If the chunk starts with ‘0’ and is more than one digit: skip. (This is the ‘no leading zeros’ tax.)
  • Parse current chunk as long (just trust me, int will betray you someday).
  • If you’re at the very first digit: recurse with this number (no operator yet).
  • Otherwise recurse 3 times:
    • For ‘+’: evaluated + curr, prev = curr
    • For ‘-‘: evaluated – curr, prev = -curr
    • For ‘*’: evaluated – prev + prev * curr, prev = prev * curr (the sacred precedence dance)