Generate Parentheses Unique Solution fix

Question

I was trying to solve this leetcode 22 problem: Generate parentheses with a given number n. I know there are other ways to solve the problem; I just want to know why mathematically my algorithm don't work.

I'm trying to place the left open parenthesis in every valid position by swapping it with the right parenthesis until the string ((())) gets to ()()(). It works for up to 3 but not above.

vector<string> generateParenthesis(int n) {

    vector<string> fin;
    string baseString = "";

    for(int i = 0; i < n; i++) {
        baseString = "(" + baseString + ")";
    }
    fin.push_back(baseString);

    for(int l = n - 1; l > 0; l--) {
        int r = n;
        while (r < baseString.size() - 1) {
            // cout << "something";
            string cst = baseString;
            char temp = cst[r];
            cst[r] = cst[l];
            cst[l] = temp;
            r++;
            fin.push_back(cst);
        }
    }

    return fin;
}

Can anybody explain why it couldn't generate all combinations, and if it can be extended to do so?

Answer 1

The algorithm cannot work correctly for larger 𝑛 because in every iteration of the inner loop the cst string is only one swap different from baseString, and that baseString never changes after it has been built in the first loop.

So for instance, for 𝑛=4, baseString will be set to (((()))). The algorithm will not be able to produce ()()()() because that would require at least two swaps when starting from baseString.

Another way to see why it cannot work is that the number of created strings is 1 + (𝑛─1)², while the expected number of strings is 𝐶_𝑛, i.e. the Catalan number.