Advertisement
Ta7a99

Untitled

Jan 20th, 2022
812
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<string> generateParenthesis(int n) {
  4.         set<string> ans;
  5.         vector<string> anss;
  6.         string s;
  7.         s.push_back('(');
  8.         backtrack(ans, s, n-1, n);
  9.         for(auto item: ans){
  10.             anss.push_back(item);
  11.         }
  12.         return anss;
  13.     }
  14.    
  15.     void backtrack(set<string> &ans, string s, int sumR, int sumL){
  16.         if(!valid(s))
  17.             return;
  18.         if(sumR==0 && sumL==0){
  19.             ans.insert(s);
  20.             return;
  21.         }
  22.        
  23.         for(int i = 0;i < (sumR + sumL);i++){
  24.             if(sumR>0){
  25.                 s.push_back('(');
  26.                 backtrack(ans,s,sumR-1, sumL);
  27.                 s.pop_back();
  28.             }
  29.             if(sumL>0){
  30.                 s.push_back(')');
  31.                 backtrack(ans,s,sumR,sumL-1);
  32.                 s.pop_back();
  33.             }
  34.         }
  35.     }
  36.    
  37.     bool valid(string s){
  38.         int sum = 0;
  39.         for(char c: s){
  40.             if(c=='(') sum++;
  41.             else sum--;
  42.            
  43.             if(sum<0) return false;
  44.         }
  45.         return true;
  46.     }
  47. };
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement