PPractick

The problem

A math-puzzle app shows a string of digits like "123" and a target like 6. The player must insert +, - or * between digits, or nothing, which joins digits into longer numbers, to make an expression equal to the target. The app needs all solutions. Operands can't have leading zeros ("05" is not allowed, but "0" is), and * binds tighter than + and -. The backtracking trick for precedence is to track both the running value and the last operand: to apply *, undo the last operand and add last × current instead.

Example: "123", target 6 → "1*2*3", "1+2+3".

Function signature

vector<string> addOperators(const string& num, int target);  // shown sorted here; any order is fine

Test cases

Input (num, target)	Output (sorted)	Explanation
("123", 6)	1*2*3 1+2+3
("232", 8)	2*3+2 2+3*2	* binds tighter
("105", 5)	1*0+5 10-5	"05" isn't a valid operand
("00", 0)	0*0 0+0 0-0
("3456237490", 9191)	(none)

(Confirm: operators are +, - and * only, placed between digits; no unary minus; operands have no leading zeros; values can exceed 32 bits, so use 64-bit arithmetic.)

How interviewers phrase it

• "Given a digit string num and an integer target, return all possibilities to insert the binary operators '+', '-' and/or '*' between the digits so the expression evaluates to target" (LeetCode 282).

Clarifying questions to ask

1. Can digits be concatenated into multi-digit operands? (Yes.)
2. Are leading zeros allowed in operands? (No, except the number 0 itself.)
3. How long can num be? (Up to 10 digits, so the search is at most about 4⁹ operator choices.)

Follow-ups to expect

1. "How do you handle multiplication precedence without parsing?"
2. "How do you prevent leading zeros?"
3. "Why 64-bit?"
4. "Complexity?"
5. "Can the first operand have a sign?"

Related questions

• Letter Combinations of a Phone Number Hard
• Palindrome partitioning Hard
• Word Search Hard
• N Queen Hard
• Rat in a Maze Hard
• M Coloring Problem Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in