Parentheses

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

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

For n=2

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();
    }
}