Have a question about backtracking for parsing string

user_5651595 0
Viewed 31

Given a string of numbers, you need to parse this string and then use + or - between numbers. If the result of calculation is equal to 100, add this combo to result.

Example input: "991" Example output: ["9+91", "99+1"]

Please let me know if you have thought on this. Python is preferred. Thanks

backtracking depth-first-search
1 Answers

Let's say you have n digits, then a brute-force solution would be to try and put one of three possible cases between each two digits, the possibilities are ('+','-',''(nothing)), the time complexity of this solution is 3^(d-1), where d is the number of digits in the input string.

user_181593340
Related