Discussion on: Daily Challenge #101 - Parentheses Generator

[Daan Wilmer]

Yeah, here is the most memory efficient one I could think of:

<?php
$n = 16;
$solutions = array_fill(0, 16, []);
$solutions[0][] = '';
for ($size = 1; $size <= $n; $size++) { // $i i
    for ($nestSize = 0; $nestSize < $size; $nestSize++) {
        $tailSize = $size - $nestSize - 1;
        $nestPossibilities = count($solutions[$nestSize]);
        $tailPossibilities = count($solutions[$tailSize]);
        for ($i = 0; $i < $nestPossibilities; $i++) {
            for ($j = 0; $j < $tailPossibilities; $j++) {
                $solutions[$size][] = '(' . $solutions[$nestSize][$i] . ')' . $solutions[$tailSize][$j];
            }
        }
    }
}

for ($i = 1; $i <= $n; $i++) {
    $count = count($solutions[$i]);
    printf("%02d: %d\n", $i, $count);
}

It now fails with a different amount of memory allocated, but still doesn't reach 16.

With the way it grows, I'm guessing the number of strings for 16 pairs of parentheses to be around 30 million. With each string being 33 characters (16 opening + 16 closing parenthesis, + 1 null terminator) I'm looking at almost 8 GB of memory for the strings alone. No wonder my laptop can't compute it.