Permutations — LeetCode #46

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Solutions:

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first=0):
            if first == n:
                output.append(nums[:])
            for i in range(first, n):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]

        n = len(nums)
        output = []
        nums.sort()
        backtrack()
        return output

C#

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> output = new List<IList<int>>();
        void Backtrack(int first = 0) {
            if (first == nums.Length) {
                output.Add(nums.ToList());
            }
            for (int i = first; i < nums.Length; i++) {
                (nums[first], nums[i]) = (nums[i], nums[first]);
                Backtrack(first + 1);
                (nums[first], nums[i]) = (nums[i], nums[first]);
            }
        }
        Array.Sort(nums);
        Backtrack();
        return output;
    }
}

Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> output = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(0, nums, output);
        return output;
    }

    private void backtrack(int first, int[] nums, List<List<Integer>> output) {
        if (first == nums.length) {
            List<Integer> curr = new ArrayList<>();
            for (int num : nums) {
                curr.add(num);
            }
            output.add(curr);
        }
        for (int i = first; i < nums.length; i++) {
            int temp = nums[first];
            nums[first] = nums[i];
            nums[i] = temp;
            backtrack(first + 1, nums, output);
            temp = nums[first];
            nums[first] = nums[i];
            nums[i] = temp;
        }
    }
}

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let output = [];
    function backtrack(first = 0) {
        if (first === nums.length) {
            output.push([...nums]);
        }
        for (let i = first; i < nums.length; i++) {
            [nums[first], nums[i]] = [nums[i], nums[first]];
            backtrack(first + 1);
            [nums[first], nums[i]] = [nums[i], nums[first]];
        }
    }
    nums.sort();
    backtrack();
    return output;
};

Typescript

function permute(nums: number[]): number[][] {
    let output: number[][] = [];
    function backtrack(first = 0): void {
        if (first === nums.length) {
            output.push([...nums]);
        }
        for (let i = first; i < nums.length; i++) {
            [nums[first], nums[i]] = [nums[i], nums[first]];
            backtrack(first + 1);
            [nums[first], nums[i]] = [nums[i], nums[first]];
        }
    }
    nums.sort();
    backtrack();
    return output;
}

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        $output = [];
        sort($nums);
        backtrack(0, $nums, $output);
        return $output;
    }
    
}

function backtrack($first, &$nums, &$output) {
    if ($first == count($nums)) {
        $output[] = $nums;
    }
    for ($i = $first; $i < count($nums); $i++) {
        list($nums[$first], $nums[$i]) = [$nums[$i], $nums[$first]];
        backtrack($first + 1, $nums, $output);
        list($nums[$first], $nums[$i]) = [$nums[$i], $nums[$first]];
    }
}

I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some claps to support my content