Generate Parentheses

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

class Solution {
public:
    void DP(vector<string>& combinations, string curr, int numOpen, int numClose, int total) {

        // Base case
        if(curr.size() == total*2) {
            combinations.push_back(curr);
            return;
        }
        
        // If we have more pairs, continue generating combinations
        if(numOpen < total)
            DP(combinations, curr+"(", numOpen+1, numClose, total);
        
        // If we have more open pairs, continue adding closed pairs
        if(numClose < numOpen)
            DP(combinations, curr+")", numOpen, numClose+1, total);
    }
    
    vector<string> generateParenthesis(int n) {
        // Vector to store all combinations
        vector<string> combinations;

        // Generate all combinations using 
        // Backtracking
        DP(combinations, "", 0, 0, n);
        return combinations;
    }
};