Order of combinations shouldn't matter


  • 0
    J
    /**
    * Since the order of each element in the output array shouldn't really matter, I won't bother outputting exactly the same result as the expected answer. Anyway. Correct me if I'm wrong.
    * This solution applies the Decrease and Conquer algorithm to the problem.
    * To develop this solution, consider each pair of "()" as a container. We can either place another container on one's left, right, or inside of it.
    * Then we simplify this problem to finding out the combination of different ways you place N containers.
    * At the end of the method, don't forget to get rid of all duplicate ways.
    **/
    /**
     * @param {number} n
     * @return {string[]}
     */
    var generateParenthesis = function(n) {
        if(n <= 1){
            return ["()"];
        }
        var a = [], r = [];
        //recursively decrease this problem into a smaller one
        r = generateParenthesis(n - 1);
        //expand the current result by adding 3 combinations on the ['left', 'right', 'inside'] pattern to each current combination.
        for(i = 0; i < r.length; i ++){
            a = a.concat(["()"+r[i], r[i]+"()", "("+r[i]+")"]);
        }
        //filter out duplicates and return
        return a.filter(function(value, index, b){
            return b.indexOf(value) === index;
        });
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.