Parentheses

Write a function to generate all possible n pairs of balanced parentheses.

image

Example: Given n=1 –> output should be:

()

Example: Given n=2

(())
()()

Example: Given n=3

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

Approach (Binary)

If we consider “(“ as 0, and we consider “)” as 1 -  the output would be all the binary combinations that make valid parentheses statement.

For n=1

image

For n=2

image

Approach (Recursion)

We can guess that a recursion would be easier to implement comparing to an iterative solution since the output of N can be constructed from the output of N-1.

Here’s n=1:

()

n=2 is based on n=1

(())
()()

n=3 is based on n=2

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

The recursion would probably be something like:

  1. Base case, return result for n=1, which is a list with “()”
  2. Get result for n-1. Such that when n=2, we get a get a list with “()”
  3. For each item in the list
    1. Add “()” after every open parentheses. For n=2 we get (())
    2. Add “()” to the beginning. For n=2 we get ()()
    3. Remove duplications

here’s the stack (look from the bottom up):

  • ParenthesesBuilderRecursive (3) - Extends { (()),  ()() } into …
    • ParenthesesBuilderRecursive (2) – Extends { “()” } into  { (()),  ()() }
      • ParenthesesBuilderRecursive (1) – returns  { “()” }


Tests

public class ParenthesesBuilderTest {
private static final boolean USE_BINARY = false;
@Test
public void getPairs_oneItem() throws Exception {
ParenthesesBuilder builder = createBuilder(USE_BINARY);

final String[] pairs = builder.getPairs(1);
assertEquals(1, pairs.length);

assertEquals("()", pairs[0]);
}


@Test
public void getPairs_twoItem() throws Exception {
ParenthesesBuilder builder = createBuilder(USE_BINARY);

final String[] pairs = builder.getPairs(2);

printParis(pairs);
assertEquals(2, pairs.length);

assertEquals("(())", pairs[0]);
assertEquals("()()", pairs[1]);
}

@Test
public void getPairs_threeItem() throws Exception {
ParenthesesBuilder builder = createBuilder(USE_BINARY);
final String[] pairs = builder.getPairs(3);

printParis(pairs);
assertEquals(5, pairs.length);
}

@Test
public void getPairs_fourItem() throws Exception {
ParenthesesBuilder builder = createBuilder(USE_BINARY);
final String[] pairs = builder.getPairs(4);

printParis(pairs);
}

private void printParis(String[] pairs) {
for (String s: pairs) {
System.out.println(s);
}
}

private ParenthesesBuilder createBuilder(boolean useBinary) {
if (useBinary) {
return new ParenthesesBuilderBinary();
}
return new ParenthesesBuilderRecursive();
}
}

Solution (Binary)

public class ParenthesesBuilderBinary implements ParenthesesBuilder{
@Override
public String[] getPairs(int n) {
List<String> result = new ArrayList<>();

final int numberOfBits = n * 2;
int bitComboCount = (int) Math.pow(2, numberOfBits);

// for every bit.. given n=1, combos would be: 00..01..10..11
for (int currentBit = 0; currentBit < bitComboCount; currentBit++) {
Boolean[] combos = tryGetCombos(currentBit, numberOfBits);
Boolean valid = combos != null && ParenthesesValidation.checkValid(combos);
if (valid) {
char[] chars = new char[numberOfBits];
for (int j = 0; j < combos.length; j++) {
chars[j] = combos[j] ? '(' : ')';
}
result.add(String.copyValueOf(chars));
}
}

return result.toArray(new String[0]);
}

private static Boolean[] tryGetCombos(int currentBit, int numberOfBits) {
int balance = 0;

Boolean[] combos = new Boolean[numberOfBits];
for (int index = 0; index < numberOfBits; index++) {
int factor = 1 << index;
Boolean bitIsSet = (factor & currentBit) > 0;
if (bitIsSet) {
balance++;
}
else{
balance--;
}
combos[index] = bitIsSet;
}

return balance == 0 ? combos : null;
}
}
public class ParenthesesValidation {
public static Boolean checkValid(Boolean[] combos) {
Stack<Boolean> stack = new Stack<>();
for (int i = 0; i < combos.length; i++) {
final Boolean open = combos[i];
if (open) {
stack.add(true);
} else {
if (stack.isEmpty()) {
return false;
} else {
stack.pop();
}
}
}
return true;
}
}

Solution (Recursion)

public class ParenthesesBuilderRecursive implements ParenthesesBuilder {
@Override
public String[] getPairs(int n) {
/*
1 = ()
2 - ()(), (())
3 - ()()(), (()()), (())(), ()(()), ((()))

Can we build solution for n based on n-1?
*/

final Set<String> result = getPairsRecursive(n);

return result.toArray(new String[0]);
}

private HashSet<String> getPairsRecursive(int index) {

final HashSet<String> result = new HashSet<>();

if (index == 0) {
return result;
}
if (index == 1) {
result.add("()");
return result;
}

final Set<String> previousPairs = getPairsRecursive(index - 1);

for (String previousItem : previousPairs) {
// Add to the beginning
addToSet(result, String.format("()%s", previousItem));

// Add after every open Parentheses
for (int j = 0; j < previousItem.length(); j++) {
Character c = previousItem.charAt(j);
if (c == '(') {
String s = addParenthesesAtLocation(previousItem, j + 1);
addToSet(result, s);
}
}
}
return result;
}

private void addToSet(HashSet<String> result, String format) {
if (!result.contains(format)) {
result.add(format);
}
}

private String addParenthesesAtLocation(String previousItem, int index) {
StringBuilder sb = new StringBuilder(previousItem);
sb.insert(index, "()");
return sb.toString();
}
}

Comments