#include <iostream>
#include <vector>
#include <string>
/*
Generate all valid parentheses combinations for a given n.
The algorithm uses backtracking:
- At any point, we may add '(' if we still have some left to place.
- We may add ')' only if it won't break correctness:
meaning we already placed more '(' than ')'.
This ensures we never build invalid partial strings,
which keeps the search efficient and avoids unnecessary work.
*/
// A helper function that performs the recursive construction.
void buildParentheses(
int openRemaining, // how many '(' we can still add
int closeRemaining, // how many ')' we can still add
std::string& current, // the current partial string
std::vector<std::string>& result // where we store completed valid strings
) {
// When both counters reach zero, we have a complete valid combination.
if (openRemaining == 0 && closeRemaining == 0) {
result.push_back(current);
return;
}
// If we can still place an opening parenthesis, do so.
if (openRemaining > 0) {
current.push_back('(');
buildParentheses(openRemaining - 1, closeRemaining, current, result);
current.pop_back(); // backtrack
}
// We can place a closing parenthesis only if it keeps the string valid.
// That means we must have placed more '(' than ')' so far.
if (closeRemaining > openRemaining) {
current.push_back(')');
buildParentheses(openRemaining, closeRemaining - 1, current, result);
current.pop_back(); // backtrack
}
}
// A convenience wrapper that returns all valid parentheses combinations.
std::vector<std::string> generateParentheses(int n) {
std::vector<std::string> result;
std::string current;
// We start with n '(' and n ')' available.
buildParentheses(n, n, current, result);
return result;
}
int main() {
int n = 3; // You can change this to any positive integer.
auto combos = generateParentheses(n);
std::cout << "Valid parentheses combinations for n = " << n << ":\n";
for (const auto& s : combos) {
std::cout << " " << s << "\n";
}
}
/*
run:
Valid parentheses combinations for n = 3:
((()))
(()())
(())()
()(())
()()()
*/
