Approach
Depth-first search
For Remove Invalid Parentheses, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 49 lines of Python from the credited upstream file 301.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected, together with recursive traversal.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def removeInvalidParentheses(self, s: str) -> list[str]:3 4 def getLeftAndRightCounts(s: str) -> tuple[int, int]:5 """Returns how many '(' and ')' need to be deleted."""6 l = 07 r = 08 9 for c in s:10 if c == '(':11 l += 112 elif c == ')':13 if l == 0:14 r += 115 else:16 l -= 117 18 return l, r19 20 def isValid(s: str):21 opened = 0 22 for c in s:23 if c == '(':24 opened += 125 elif c == ')':26 opened -= 127 if opened < 0:28 return False29 return True 30 31 ans = []32 33 def dfs(s: str, start: int, l: int, r: int) -> None:34 if l == 0 and r == 0 and isValid(s):35 ans.append(s)36 return37 38 for i in range(start, len(s)):39 if i > start and s[i] == s[i - 1]:40 continue41 if r > 0 and s[i] == ')': 42 dfs(s[:i] + s[i + 1:], i, l, r - 1)43 elif l > 0 and s[i] == '(': 44 dfs(s[:i] + s[i + 1:], i, l - 1, r)45 46 l, r = getLeftAndRightCounts(s)47 dfs(s, 0, l, r)48 return ans49