/*
 * 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]
 *
 *  ]
*/

const { assert } = require('../../util/js');

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute = function(nums) {
    
    const permuRecursive = (soFar, rest, perm) => {
        if (rest.length === 0) {
            perm.push(soFar);
        }
        
        for(let i = 0; i < rest.length; i++) {
            const rem = [...rest.slice(0, i), ...rest.slice(i+1)];
            permuRecursive([...soFar, rest[i]],  rem, perm);
        }
    }
    const result = [];
    permuRecursive([], nums, result);
    return result;
    
};

/* Test Case 1
 * Input: [1,2,3]
 * Output:
 * [
 *    [1,2,3],
 *    [1,3,2],
 *    [2,1,3],
 *    [2,3,1],
 *    [3,1,2],
 *    [3,2,1]
 *
 *  ]
 */
x = [1,2,3];
sol = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]];
assert(JSON.stringify(permute(x)) === JSON.stringify(sol), `Output: ${JSON.stringify(sol)}`);