Finding All Combinations of Well-Formed Brackets

Finding all combinations of well-formed brackets

Took a crack at it.. C# also.

public void Brackets(int n) {
    for (int i = 1; i <= n; i++) {
        Brackets("", 0, 0, i);
    }
}

private void Brackets(string output, int open, int close, int pairs) {
    if((open==pairs)&&(close==pairs)) {
        Console.WriteLine(output);
    } else {
        if(open<pairs)
            Brackets(output + "(", open+1, close, pairs);
        if(close<open)
            Brackets(output + ")", open, close+1, pairs);
    }
}

The recursion is taking advantage of the fact that you can never add more opening brackets than the desired number of pairs, and you can never add more closing brackets than opening brackets..

Bracket Combinations

You are looking for Catalan numbers (OEIS A000108). The only problem is that these numbers grow fast (~ 4**n), that's why
you should be careful with integer overflow:

    public static int BracketCombinations(int num) {
      if (num < 0 || num > 19)
        throw new ArgumentOutOfRangeException(nameof(num));

      long result = 1;

      for (int k = 1; k < num; ++k)
        result = 2 * (2 * k + 1) * result / (k + 2);

      return (int)result;
    }

Demo:

    var report = string.Join(Environment.NewLine, Enumerable
      .Range(0, 20)
      .Select(x => $"{x,2} => {BracketCombinations(x)}"));

    Console.Write(report);

Outcome:

 0 => 1
 1 => 1
 2 => 2
 3 => 5
 4 => 14
 5 => 42
 6 => 132
 7 => 429
 8 => 1430
 9 => 4862
10 => 16796
11 => 58786
12 => 208012
13 => 742900
14 => 2674440
15 => 9694845
16 => 35357670
17 => 129644790
18 => 477638700
19 => 1767263190

Generating all combinations of a list of strings with both parentheses and an operator being permuted, too

You can use itertools.combinations to pick operands from the given list, use itertools.product to produce combinations of operators, and use itertools.product again to produce all mixes of operands and operators, and use a for loop that keeps nesting lists according to the chosen operands and operators to build the desired output:

from itertools import combinations, product
def expressions(l, n):
    for (operations, *operands), operators in product(
            combinations(l, n), product(('AND', 'OR'), repeat=n - 1)):
        for operation in zip(operators, operands):
            operations = [operations, *operation]
        yield operations

so that list(expressions(['A','B','C','D'], 3)) returns:

[[['A', 'AND', 'B'], 'AND', 'C'],
 [['A', 'AND', 'B'], 'OR', 'C'],
 [['A', 'OR', 'B'], 'AND', 'C'],
 [['A', 'OR', 'B'], 'OR', 'C'],
 [['A', 'AND', 'B'], 'AND', 'D'],
 [['A', 'AND', 'B'], 'OR', 'D'],
 [['A', 'OR', 'B'], 'AND', 'D'],
 [['A', 'OR', 'B'], 'OR', 'D'],
 [['A', 'AND', 'C'], 'AND', 'D'],
 [['A', 'AND', 'C'], 'OR', 'D'],
 [['A', 'OR', 'C'], 'AND', 'D'],
 [['A', 'OR', 'C'], 'OR', 'D'],
 [['B', 'AND', 'C'], 'AND', 'D'],
 [['B', 'AND', 'C'], 'OR', 'D'],
 [['B', 'OR', 'C'], 'AND', 'D'],
 [['B', 'OR', 'C'], 'OR', 'D']]

Understanding function to generate parentheses

It helps me to see visually how the calls are being stacked. I added a parameter String depth to the call and printed out depth + str on each call, adding four spaces to each depth parameter for a new call. This gives us a good view of the call order.

Here's the code for it:

recursion(3, new String(), solutions, "");
//...
private static void recursion(int n, String str, ArrayList<String> sol, String depth) {
    System.out.println(depth + str);
    //...
        if(left == right)
            recursion(n, str + "(", sol, depth + "    ");
        else if(right < left) {
            if(left < n)
                recursion(n, str + "(", sol, depth + "    ");
            recursion(n, str + ")", sol, depth + "    ");
}

---

And here's what it prints out:

(
    ((
        (((
            ((()
                ((())
                    ((()))
        (()
            (()(
                (()()
                    (()())
            (())
                (())(
                    (())()
    ()
        ()(
            ()((
                ()(()
                    ()(())
            ()()
                ()()(
                    ()()()

Each level of recursion adds another indent to the output. If two outputs are at the same level of indentation, then they were both called from the same level of recursion.

Here's another visual:

Note that each node is a deeper level of recursion and each time a child node comes straight down out of a parent node, it doesn't split into two recursive paths. That is, the parent node only calls recursion once.

Generate all balanced parenthesis for a given N

//c++ program to print all the combinations of 
balanced parenthesis.
#include <bits/stdc++.h>
using namespace std;
//function which generates all possible n pairs 
of balanced parentheses.
//open : count of the number of open parentheses 
used in generating the current string s.
//close : count of the number of closed 
parentheses used in generating the current string 
s.
//s : currently generated string/
//ans : a vector of strings to store all the 
valid parentheses.
void generateParenthesis(int n, int open, int 
close, string s, vector<string> &ans){
  //if the count of both open and close 
parentheses reaches n, it means we have generated 
a valid parentheses.
  //So, we add the currently generated string s 
to the final ans and return.
if(open==n && close==n){
    ans.push_back(s);
    return;
}  
  //At any index i in the generation of the 
string s, we can put an open parentheses only if 
its count until that time is less than n.
if(open<n){
    generateParenthesis(n, open+1, close, s+"{", 
ans);
}
//At any index i in the generation of the string             
s, we can put a closed parentheses only if its 
count until that time is less than the count of 
open parentheses.
if(close<open){
    generateParenthesis(n, open, close+1, s+"}", 
ans);
}
  
}
int main() {
int n = 3;
  //vector ans is created to store all the 
possible valid combinations of the parentheses.
vector<string> ans;
  //initially we are passing the counts of open 
and close as 0, and the string s as an empty 
string. 
generateParenthesis(n,0,0,"",ans);
  //Now, here we print out all the combinations.
for(auto s:ans){
    cout<<s<<endl;
}
return 0;
}

What's time complexity of this algorithm for generating all possible valid parentheses?

If you could do a bit alteration in your validation method you can save a significant execution time for large value of n. You can use a counter instead of a stack to check for validation.
something like this

 private boolean isValid(String str)
  {
    // Input checking.
    if (str == null || str.length() < 2)
    {
      return false;
    }
    int ct = 0;
    for (int i = 0; i < str.length(); i++)
    {
      char curr = str.charAt(i);
      if (ct < 0)
      {
        return false;
      }
      if (curr == '(')
      {
        ct++;
      }
      else if (curr == ')')
      {
        ct--;
      }
    }
    if (ct != 0 || ct < 0)
    {
      return false;
    }
    else
    {
      return true;
    }
  }

I ran it on my machine and the time saving for n=13 is around 2 sec and with this method in place the total execution time for the algorithm is less than 2 sec.
For n=15 time saving is around 12 sec.

This will not only save time but will also save significant amount of memory.

leetcode Generate Parentheses Algorithm

The idea is to start with ( and the variable left and right to record the number of ( and ) respectively.

Here was my solution:

public class Solution {
    private void helper(List<String> res, String present, int left, int right, int n) {
        // When you've finished adding all parenthesis
        if (left == n and right == n) {
            res.push_back(str);
            return;
        }
        // You have left parenthesis available to add
        if (left < n) {
            helper(res, present + "(", left + 1, right, n);
        }
        // You can add right parenthesis only when you have more left parenthesis already added otherwise it won't be balanced
        if (left > right) {
            helper(res, present + ")", left, right + 1, n);
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        if (n == 0) {
            return res;
        }
        helper(res, "", 0, 0, n);
        return res;
    }
}

---

Related Topics