LeetCode 22. 括号生成：DFS递归代码调试求助

Hey there! Let's dig into why your DFS approach is generating invalid parentheses combinations. The core issue is how you're modifying the string s during recursive calls.

The Problem: Accidental String Mutation #

In your code, when you call dfs(result, s += "(", num_left - 1, num_right);, the s += "(" doesn't just create a new string for the recursive call—it modifies the s variable in the current function's scope.

Here's what goes wrong step by step:

1. Start with s = "", num_left = n, num_right = n.
2. Enter the num_left > 0 branch, run s += "(", so s becomes "(" in this function.
3. After the recursive call returns, move to the num_right branch—but now s is already "(", not the original empty string. When you run s += ")", you're appending to the modified s, leading to unexpected combinations and extra parentheses.

This mutation of the current function's s causes cross-contamination between your left and right bracket branches.

The Fix: Pass New Strings Instead of Modifying #

Instead of changing the existing s, create a new string for each recursive call using s + "(" and s + ")". This way, the original s in the current function stays intact, and each recursive branch gets a fresh copy of the string with the new bracket added.

Here's the corrected code:

#include <vector>
#include <string>
using namespace std;

vector<string> generateParenthesis(int n) {
    vector<string> result;
    dfs(result, "", n, n);
    return result;
}

void dfs(vector<string> &result, string s, int num_left, int num_right){
    // Base case: no brackets left to add
    if(num_left == 0 && num_right == 0){
        result.push_back(s);
        return; // Exit early to skip unnecessary checks
    }
    
    // Add left bracket if we have remaining ones
    if(num_left > 0){
        dfs(result, s + "(", num_left - 1, num_right);
    }
    
    // Add right bracket only if we have more right brackets left than left
    if(num_right > num_left){
        dfs(result, s + ")", num_left, num_right - 1);
    }
}

Extra Improvements: #

• Added a return after pushing the valid string to the result—this avoids running subsequent if checks when we're done with this branch, making the code a bit more efficient.
• Removed the redundant num_right > 0 check in the second if—since num_right > num_left already implies num_right is positive (because num_left can't be negative).

This should generate all valid parentheses combinations correctly now! For n=3, you'll get the exact output you're expecting: ["((()))", "(()())", "(())()", "()(())", "()()()"].

内容的提问来源于stack exchange，提问作者chibiw3n