Permutations

Leetcode Problem 46: Permutations

Problem Summary

Given an array of distinct integers, return every possible ordering (permutation) of those numbers. The result can be returned in any order and must include all n factorial arrangements.

Techniques

• Array
• Backtracking

Solution

function backtrackingPermutation(
    results: number[][],
    elements: number[],
    start: number
) {
    if (start === elements.length) {
        results.push([...elements]);
        return;
    }

    for (let i = start; i < elements.length; i++) {
        [elements[start], elements[i]] = [elements[i], elements[start]]
        backtrackingPermutation(results, elements, start + 1);
        [elements[start], elements[i]] = [elements[i], elements[start]]
    }
}

function permute(nums: number[]): number[][] {
    const results: number[][] = [];
    backtrackingPermutation(results, nums, 0);
    return results;
}

console.log(permute([1, 2, 3]));