46. Permutations

Medium

Problem Description

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

Examples

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]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def permute(nums: List[int]) -> List[List[int]]:
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        
        for i in range(start, len(nums)):
            # Swap elements to create permutation
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            # Backtrack by swapping back
            nums[start], nums[i] = nums[i], nums[start]
    
    result = []
    backtrack(0)
    return result

Java Solution


class Solution {
    private List> result = new ArrayList<>();
    
    public List> permute(int[] nums) {
        backtrack(nums, 0);
        return result;
    }
    
    private void backtrack(int[] nums, int start) {
        if (start == nums.length) {
            List permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }
        
        for (int i = start; i < nums.length; i++) {
            // Swap elements to create permutation
            swap(nums, start, i);
            backtrack(nums, start + 1);
            // Backtrack by swapping back
            swap(nums, start, i);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

C++ Solution


class Solution {
public:
    vector> permute(vector& nums) {
        vector> result;
        backtrack(nums, 0, result);
        return result;
    }
    
private:
    void backtrack(vector& nums, int start, vector>& result) {
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }
        
        for (int i = start; i < nums.size(); i++) {
            // Swap elements to create permutation
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, result);
            // Backtrack by swapping back
            swap(nums[start], nums[i]);
        }
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
    
    const backtrack = (start) => {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        
        for (let i = start; i < nums.length; i++) {
            // Swap elements to create permutation
            [nums[start], nums[i]] = [nums[i], nums[start]];
            backtrack(start + 1);
            // Backtrack by swapping back
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    };
    
    backtrack(0);
    return result;
};

C# Solution


public class Solution {
    private IList> result = new List>();
    
    public IList> Permute(int[] nums) {
        Backtrack(nums, 0);
        return result;
    }
    
    private void Backtrack(int[] nums, int start) {
        if (start == nums.Length) {
            result.Add(new List(nums));
            return;
        }
        
        for (int i = start; i < nums.Length; i++) {
            // Swap elements to create permutation
            Swap(nums, start, i);
            Backtrack(nums, start + 1);
            // Backtrack by swapping back
            Swap(nums, start, i);
        }
    }
    
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking to generate all possible permutations. Here's how it works:

Key points: