backtracking::generate_parentheses Class Reference

generate_parentheses class More...

Collaboration diagram for backtracking::generate_parentheses:

Public Member Functions
std::vector< std::string >	generate (int n)
	wrapper interface

Private Member Functions
void	makeStrings (std::string str, int n, int closed, int open)
	function that adds parenthesis to the string.

Private Attributes
std::vector< std::string >	res
	Contains all possible valid patterns.

Detailed Description

generate_parentheses class

Member Function Documentation

generate()

std::vector< std::string > backtracking::generate_parentheses::generate

(

int

n

)

wrapper interface

Parameters

n	number of pairs of parentheses

Returns

all well-formed pattern of parentheses

                                                         {
    backtracking::generate_parentheses::res.clear();
    std::string str = "(";
    generate_parentheses::makeStrings(str, n, 0, 1);
    return res;
}

Here is the call graph for this function:

makeStrings()

void backtracking::generate_parentheses::makeStrings ( std::string str, int n, int closed, int open )

private

function that adds parenthesis to the string.

Parameters

str	string build during backtracking
n	number of pairs of parentheses
closed	number of closed parentheses
open	number of open parentheses

                                                                           {
    if (closed > open)  // We can never have more closed than open
        return;
 
    if ((str.length() == 2 * n) &&
        (closed != open)) {  // closed and open must be the same
        return;
    }
 
    if (str.length() == 2 * n) {
        res.push_back(str);
        return;
    }
 
    makeStrings(str + ')', n, closed + 1, open);
    makeStrings(str + '(', n, closed, open + 1);
}

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• backtracking/generate_parentheses.cpp