def generateParenthesis(n):
stack = []
def backtrack(openN, closeN, s):
if closeN == 0:
stack.append(s)
return
if openN > 0:
s += '('
openN -= 1
backtrack(openN, closeN, s)
if closeN > openN:
s += ')'
closeN -= 1
backtrack(openN, closeN, s)
backtrack(n,n,'')
return stack
print(generateParenthesis(3))
the output is
['((()))', '((()))', '(()())', '(()())', '()(())', '()(())', '()()()', '()()()']
but I expect is
['((()))', '(()())', '(())()', '()(())', '()()()']
Why there is a duplicated value?
def generateParenthesis(n):
stack = []
def backtrack(openN, closeN, s):
# If no more closing parentheses are needed, add the sequence to the stack
if closeN == 0:
stack.append(s)
return
# If there are open parentheses to add, add one and recurse
if openN > 0:
backtrack(openN - 1, closeN, s + '(')
# If the number of closing parentheses needed is greater than the number of opening ones,
# it's safe to add a closing parenthesis and recurse
if closeN > openN:
backtrack(openN, closeN - 1, s + ')')
# Start the recursive process with the full count of opening and closing parentheses
backtrack(n, n, "")
return stack
# Example usage
print(generateParenthesis(3))
This is ChatGPT's result. I think the operation of the code is same as mine. But I don't know why the result is different.
The difference is that in your version, the local variable openN is mutated within the current call frame: openN -= 1 while ChatGPT's version, it's only changed as a recursive call parameter:
# ChatGPT -- correct
# ...
if openN > 0:
backtrack(openN - 1, closeN, s + '(')
# ^^^^^^^^^
# ...
In your version, the if structure is such that in a given frame, doing openN -= 1 in the top if will affect the openN value used in the bottom if, making it one less than it should be:
# Your version -- incorrect
# ...
if openN > 0:
s += '('
openN -= 1 # change openN
backtrack(openN, closeN, s)
if closeN > openN: # this condition is now less strict by 1
s += ')'
closeN -= 1
backtrack(openN, closeN, s) # call backtrack(openN - 1, closeN - 1, s)
# ...
On the bottom line, the call we want is backtrack(openN, closeN - 1, s) but yours is off by one if the top branch ran, decrementing openN by one and corrupting its value for the rest of the current frame.
Not only that, but the condition guarding the bottom recursive call that used to be if closeN > openN: in the correct version is now if closeN > openN - 1:. This condition is easier to fulfill, accounting for the extra results (more recursive calls == more results in the output).
The general rule of thumb at play here is: don't mutate values unless you have good reason to. Each recursive call frame needs to be computed based purely on its parameters. If those parameters are mutated locally, particularly in an if, the logic can easily change such that you're computing the result for a different call frame, or in this case, making a recursive call that doesn't make sense for the algorithm (the count of open/closed needs to stay in sync with s).
Many languages don't allow mutating values, and other languages make it easier to declare parameter values as constants. Writing this in C++ as void backtrack(const int openN, const int closeN, const std::string &s) would lead to safer logic, preventing the unnecessary -= at the compiler level.
Note that closeN -= 1 isn't technically a bug since closeN is never used after the mutation. But it's still poor style since it could easily lead to a bug in the future if you decided to use it after a refactor or functionality change, so best practice would be not to mutate it.
If you don't like the "busy" recursive function calls with subtraction and addition inside the argument list, you can create new variables for the current values. Just be careful to copy correctly if these values are non-primitive (not the case here).
Another general tip: print values or use a debugger to see the differences between the two versions. Adding print(closeN, openN) above the if closeN > openN: condition makes one of the differences clear.