Return all valid paren strings with a given length

Question

The problem is

Given a non-negative integer n, return all valid parentheses strings with n open parens and n close parens.

My algorithm (represented by the MySolution class below) keeps a count of the open parentheses on the stack, and does a recursive depth-first search of possible strings.

Another algorithm (represented by the TheirSolution class) uses a similar strategy, but their solution reliably runs about twice as fast, when optimization is turned off. The outputs are identical.

The major difference is that their solution copies the current string on every recursive call to Dfs, so they never have to delete any characters from the end of strings; they just throw away the whole copy when the current stack frame ends. Another difference is that they keep track of the number of open parens left to use (pos) and close parens left to use (neg) explicitly, while my code does so implicitly.

Their code involves roughly the same number of recursions that mine does.

int main()
{
    constexpr int n_parens = 11;
    MySolution sol1;
    TheirSolution sol2;
    sol1.generateParenthesis(n_parens);
    sol2.generateParenthesis(n_parens);
}

Produces (with debug config)

There were 290511 recursions.
Timer took 0.0245487 seconds.
There were 290510 recursions.
Timer took 0.0118699 seconds.
Program ended with exit code: 0



int main()
{
    constexpr int n_parens = 11;
    MySolution sol1;
    TheirSolution sol2;
    std::vector<std::string> v = sol1.generateParenthesis(n_parens);
    std::vector<std::string> w = sol2.generateParenthesis(n_parens);
    std::cout << (int)(v == w) << std::endl;
}

Produces (with release config)

There were 290511 recursions.
Timer took 0.00570454 seconds.
There were 290510 recursions.
Timer took 0.00704376 seconds.
1
Program ended with exit code: 0

Here's the code!

#include <iostream>
#include <chrono>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

struct Timer
{
    std::chrono::time_point<std::chrono::steady_clock> start, end;
    std::chrono::duration<float> duration;

    Timer()
    {
        start = std::chrono::high_resolution_clock::now();
    }

    ~Timer()
    {
        end = std::chrono::high_resolution_clock::now();
        duration = end - start;

        std::cout << "Timer took " << duration.count() << " seconds." << std::endl;
    }

};

class TheirSolution {
public:

    void Dfs(int deep, int border, int cnt, char c, std::vector<std::string>& v, int pos, int neg, std::string s)
    {
        n_recursions++;
        s.append(1, c);

        if (deep == border && pos == 0 && neg == 0)
        {
            v.push_back(s);
            return;
        }

        if (pos > 0)
        {
            Dfs(deep + 1, border, cnt + 1, '(', v, pos - 1, neg, s);
        }

        if (cnt > 0 && neg > 0)
        {
            Dfs(deep + 1, border, cnt - 1, ')', v, pos, neg - 1, s);
        }
    }

    std::vector<std::string> generateParenthesis(int n) {

        n_recursions = 0;
        Timer timer;

        int positive, negative;
        positive = negative = n;

        std::vector<std::string> answer;

        std::string s = "";

        Dfs(1, 2 * n, 1, '(', answer, positive - 1, negative, s);

        std::cout << "There were " << n_recursions << " recursions." << std::endl;

        return answer;
    }

private:
    long long n_recursions;
};


class MySolution {
public:
    std::vector<std::string> generateParenthesis(int _n)
    {
        Timer timer;
        n_recursions = 0;
        n = _n;
        dfs(0);
        std::cout << "There were " << n_recursions << " recursions." << std::endl;
        return ret;
    }

private:

    void dfs(int stack_count)
    {
        n_recursions++;
        if (stack_count == -1)
            return;

        else if (current_string.size() == 2*n)
        {
            if (stack_count == 0)
                ret.push_back(current_string);
            return;
        }

        if (stack_count < 2*n - current_string.size())
        {
            current_string.push_back('(');
            dfs(stack_count + 1);
            current_string.pop_back();
        }

        if (stack_count > 0)
        {
            current_string.push_back(')');
            dfs(stack_count - 1);
            current_string.pop_back();
        }
    }

    long long n_recursions;
    int n;
    std::string current_string;
    std::vector<std::string> ret;
};

int main()
{
    constexpr int n_parens = 11;
    MySolution sol1;
    TheirSolution sol2;
    sol1.generateParenthesis(n_parens);
    sol2.generateParenthesis(n_parens);
}

Answer 1

I think your implicit question was "how may I improve runtime?", in terms of CPU cycles, and in terms of memory read stalls. The only relevant timings to pay attention to seem to be the optimized runs, and in that contest you're already pretty close. Runtimes less than 10 msec suggest that you might want to do a hundred iterations of the whole test, or bump up n_parens. Do verify that switching the order of running sol{1,2} doesn't change the timings, e.g. due to cache warming effects.

This code appears to be vestigial; it may have mattered in an earlier code version:

    if (stack_count == -1)
        return;

The return appears to be dead code. I say that because there is a "positive" guard if (stack_count > 0) on the decrement of stack_count.

Overall your code seems pretty cache friendly. I don't see any obvious gotchas. This copy:

            ret.push_back(current_string);

could maybe be dispensed with, by building up the result string in the desired spot within ret. Of course, they do v.push_back(s) which is similar copying cost.

I choose to read deep as "depth", and I prefer that concise name over the clunky stack_count.

I find their profusion of redundant args somewhat ugly. However, it's a sure thing that each one is register allocated. I wonder if your repeated current_string.size() access explains the few missing milliseconds that separate the two implementations?

Your depth first search has three clauses, and three brief comments seem warranted.

The biggest change to make to this recursive approach would be to memoize the result of a given stack_count input, to avoid repeatedly computing (and recursing) for that given value. Your single-arg API is clearly simpler to memoize than TheirSolution would be.