[Algorithm] 46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:
Input: [1,2,3]

Output:

[

  [1,2,3],

  [1,3,2],

  [2,1,3],

  [2,3,1],

  [3,1,2],

  [3,2,1]

]

The idea is using recursive approach, we can define a recursive function

helper(prefix, suffix, result)

Where the prefix is: for example

[1]

suffix:

[2, 3]

So every time, we take one value from suffix, put into prefix.

The stop logic is that when suffix length is zero, then we push the prefix into result.

if (sfx.length === 0) {

     result.push(pfx);

}

/**

 * @param {number[]} nums

 * @return {number[][]}

 */

var permute = function(nums) {

    function helper (pfx, sfx, result) {

        if (sfx.length === 0) {

            result.push(pfx);

        } else {

            const len = sfx.length;

            for (let i = 0; i < len; i++) {

                helper(

                    pfx.concat(sfx[i]),

                    sfx.slice(0, i).concat(sfx.slice(i+1, sfx[len])),

                    result

                );

            }

        }

        return result;

    }

    return helper([], nums, []);

};

permute([1,2,3])

/*

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

*/

[], [1,2,3]

[1], [2,3]

[1, 2], [3], [] | [1, 3], [2] 

---> [1,2,3] | [1,2,3]

[2], [1, 3]

[2, 1], [3] | [2,3] [1]

--> [2,1,3] | [2,3,1]

[3], [1,2]

[3,1][2] | [3,2], [1]

--> [3,1,2] | [3,2,1]

巴特西

[Algorithm] 46. Permutations

最新文章

热门文章