leetcode Generate Parentheses

const solutions = [];

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    return gen(n).filter(s => s.length > 0).sort();
}

// WTF is this problem
// the result needs to be sorted as given
function gen(n) {
    if(n <= 0) {
        return [''];
    }
    if(n === 1) {
        return ["()"];
    }
    if(solutions[n]) {
        return solutions[n];
    }

    const result = [];
    // First: standby (nothing inside) (0, n-1)
    // Wrapped + standby
    // Last: wrapped (nothing after) (n-1, 0)
    for(let i = 0, k = n - 1; i <= k; ++i) {
        for(const s1 of gen(i)) {
            for(const s2 of gen(k - i)) {
                result.push(`(${s1})${s2}`)
            }
        }
    }
    solutions[n] = result;
    return result;
};