LeetCode 22. Generate Parentheses (C++)

Question

The task is taken from LeetCode. I would appreciate an assessment of whether my coding style follows good practices. I'm fairly familiar with algorithms and data structures so I'm not really looking for feedback on that end (I could probably have an early exit if nbParenthesesToClose > maxIdx - idx and I think the copy constructor of std::string is called too many a time (I show what I think that should look like at the end of the post)).

The thing I'm worried about is that I have seldomly worked with other people so I'm sometimes afraid I picked up some bad habits. Here for example, I feel like my dfs function has "too many arguments". I thought about making a lambda function that captures validParentheses for example so that I don't have to pass it around when I call the recursive dfs calls but that would make the main function bigger and having helper functions is usually considered good. Same goes for maxIdx which doesn't technically need to be passed around. So I'm a bit confused as to what I should do.

Problem statement

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example:

Input:

n = 3

Output:

["((()))","(()())","(())()","()(())","()()()"]

My solution (C++):

void dfs(
        const int idx,
        const int maxIdx,
        const int nbParenthesesToClose,
        const std::string& currString,
        std::vector<std::string>& validParentheses
    )
{
    // Sanity Check
    assert(nbParenthesesToClose >= 0);
        
    // Base Case
    if (idx == maxIdx)
    {
        if (nbParenthesesToClose == 0)
        {
            validParentheses.push_back(currString);
        }
        return;
    }
    
    // Recursive calls
    dfs(idx + 1, maxIdx, nbParenthesesToClose+1, currString + "(", validParentheses);
    if (nbParenthesesToClose > 0)
    {
        dfs(idx + 1, maxIdx, nbParenthesesToClose-1, currString + ")", validParentheses);
    }
}

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        // validParentheses will contain the valid strings
        std::vector<std::string> validParentheses;

        dfs(0, 2*n, 0, "", validParentheses);

        return validParentheses;
    }
};

If anyone wants to look at what I think the "optimised" version of the code from a algorithm point of view would be:

std::string stackToString(std::stack<char> s)
{
    // pass by copy because we'll "consume" the whole stack when doing the conversion
    std::string result;
    result.reserve(s.size());

    while (!s.empty()) {
        result.push_back(s.top());
        s.pop();
    }

    std::reverse(result.begin(), result.end());
    return result;
}

void dfs(
        const int idx,
        const int maxIdx,
        const int nbParenthesesToClose,
        std::stack<char>& currString,
        std::vector<std::string>& validParentheses
    )
{
    // Sanity Check
    assert(nbParenthesesToClose >= 0);
        
    if (idx == maxIdx)
    {
        if (nbParenthesesToClose == 0)
        {
            validParentheses.push_back(stackToString(currString));
        }
        return;
    }
    
    currString.push('(');
    dfs(idx + 1, maxIdx, nbParenthesesToClose+1, currString, validParentheses);
    currString.pop();
    if (nbParenthesesToClose > 0)
    {
        currString.push(')');
        dfs(idx + 1, maxIdx, nbParenthesesToClose-1, currString, validParentheses);
        currString.pop();
    }
}

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        // validParentheses will contain the valid strings
        std::vector<std::string> validParentheses;
        std::stack<char> currString;

        dfs(0, 2*n, 0, currString, validParentheses);

        return validParentheses;
    }
};

Chris · Accepted Answer · 2025-12-16 07:47:17Z

By default, std::stack uses std::deque as its underlying container. However, this is just the default, and any container which implements SequenceContainer as well as push_back, pop_back, and back can be provided as that underlying container.

The std::string class provides these requirements, and storing your stack as a std::string will greatly reduce the work done as you convert to a string, since there's no need to actually do any computation: you already have the underlying string.

But std::stack keeps its underlying container as a protected member which we can't access (since that would let us break the LIFO contract). So we inherit from std::stack and implement access to that container c as a member function.

#include <string>
#include <stack>

struct CharStack : std::stack<char, std::string> {
    std::string to_string() {
        return c;
    }
};

\$\begingroup\$ That's a clever usage of stack. \$\endgroup\$

Loki Astari
– Loki Astari

2025-12-16 06:39:37 +00:00
Commented 3 hours ago — Loki Astari
– Loki Astari, Commented 3 hours ago

Toby Speight · Accepted Answer · 2025-12-16 09:39:36Z

This is a review of the first code block. I might also review the second one later.

Missing includes - I needed to include <cassert>, <string> and <vector> before I could even compile the code.

This test suggests we perhaps ought to be using an unsigned type for the variable:

assert(nbParenthesesToClose >= 0);

I would suggest that idx and maxIdx also should be unsigned - probably std::size_t to match std::string::size().

We unconditionally recurse with ( even when we won't be able to close all that we open. We can avoid all those fruitless branches by being more selective:

    if (nbParenthesesToClose < maxIdx - idx) {
        dfs(idx + 1, maxIdx, nbParenthesesToClose+1, currString + '(', validParentheses);
    }

This also allows us to eliminate the test within the idx == maxIdx block, since nbParenthesesToClose now always becomes 0 when we reach the end.

Stack Exchange Network

LeetCode 22. Generate Parentheses (C++)

2 Answers 2

You must log in to answer this question.

Hot Network Questions

LeetCode 22. Generate Parentheses (C++)

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions