LeetCode 22. Generate Parentheses (C++)

Question 1

The task is taken fromLeetCode. 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 ifnbParenthesesToClose > maxIdx - idx and I think the copy constructor ofstd::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 mydfs function has "too many arguments". I thought about making a lambda function that capturesvalidParentheses for example so that I don't have to pass it around when I call the recursivedfs calls but that would make the main function bigger and having helper functions is usually considered good. Same goes formaxIdx 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 allcombinations 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;    }};

Question 2

I assume you are using dfs to learn dfs, not because it is the best approach?

Question 3

By default,std::stack usesstd::deque as its underlying container. However, this is just the default, and any container which implementsSequenceContainer as well aspush_back,pop_back, andback can be provided as that underlying container.

Thestd::string class provides these requirements, and storing your stack as astd::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.

Butstd::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 fromstd::stack and implement access to that containerc as a member function.

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

Question 4

That's a clever usage of stack.

Question 5

Seems to me like it'd be easier to just use anstd::string directly, and replacepush withpush_back andpop withpop_back.

Question 6

That's basically whatstd::stack<char, std::string> is doing.

Question 7

@Chris: yes, but in a much more roundabout way.

Question 8

Not just roundabout, but also inefficient. Printing the string now requires copying it first, rather than just directly printing it. Alsostd::stack is designed to be inherited from, but be wary ofpublicly inheriting from it.

Question 9

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 thatidx andmaxIdx also should be unsigned - probablystd::size_t to matchstd::string::size().

We unconditionally recurse with( even when we won't be able to close all the ones 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 theidx == maxIdx block, sincenbParenthesesToClose now always becomes 0 when we reach the end.

We're passing bothidx andmaxIdx through every call, but don't really need both. We just care how many characters remain to be added, which ismaxIdx - idx, so we could pass that count instead. Here's what that looks like (with some light renaming to give shorter parameters):

#include <cstddef>#include <string>#include <utility>#include <vector>void dfs(const std::size_t nchars,         const std::size_t open_parens,         std::string candidate,         std::vector<std::string>& result){    // Base Case    if (nchars == 0) {        result.push_back(std::move(candidate));        return;    }    // Recursive calls    if (open_parens < nchars) {        dfs(nchars - 1, open_parens + 1, candidate + '(', result);    }    if (open_parens > 0) {        dfs(nchars - 1, open_parens - 1, candidate += ')', result);    }}

Chris 6,9711 gold badge7 silver badges44 bronze badges · Answer 1 · 2025-12-16 15:40:12Z

By default,std::stack usesstd::deque as its underlying container. However, this is just the default, and any container which implementsSequenceContainer as well aspush_back,pop_back, andback can be provided as that underlying container.

Thestd::string class provides these requirements, and storing your stack as astd::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.

Butstd::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 fromstd::stack and implement access to that containerc as a member function.

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

Seems to me like it'd be easier to just use anstd::string directly, and replacepush withpush_back andpop withpop_back.
That's basically whatstd::stack<char, std::string> is doing.
Not just roundabout, but also inefficient. Printing the string now requires copying it first, rather than just directly printing it. Alsostd::stack is designed to be inherited from, but be wary ofpublicly inheriting from it.

Toby Speight 88.9k14 gold badges104 silver badges327 bronze badges · Answer 2 · 2025-12-16 15:09:47Z

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 thatidx andmaxIdx also should be unsigned - probablystd::size_t to matchstd::string::size().

We unconditionally recurse with( even when we won't be able to close all the ones 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 theidx == maxIdx block, sincenbParenthesesToClose now always becomes 0 when we reach the end.

We're passing bothidx andmaxIdx through every call, but don't really need both. We just care how many characters remain to be added, which ismaxIdx - idx, so we could pass that count instead. Here's what that looks like (with some light renaming to give shorter parameters):

#include <cstddef>#include <string>#include <utility>#include <vector>void dfs(const std::size_t nchars,         const std::size_t open_parens,         std::string candidate,         std::vector<std::string>& result){    // Base Case    if (nchars == 0) {        result.push_back(std::move(candidate));        return;    }    // Recursive calls    if (open_parens < nchars) {        dfs(nchars - 1, open_parens + 1, candidate + '(', result);    }    if (open_parens > 0) {        dfs(nchars - 1, open_parens - 1, candidate += ')', result);    }}

Movatterモバイル変換

Stack Exchange Network

LeetCode 22. Generate Parentheses (C++)

2 Answers2

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS