Permutations of an Array

Problem Statement

Given an array of distinct integers, return all possible permutations. Each permutation is a unique arrangement of the array’s elements, and this medium-level problem builds on recursive backtracking to explore every possible order. Imagine rearranging a set of numbered cards in every way possible—hours of fun for your brain!

Example

Input: nums = [1, 2, 3]

Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] (all 3! = 6 permutations)

Input: nums = [0, 1]

Output: [[0, 1], [1, 0]] (2! = 2 permutations)

Code

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

def permute(nums):
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]  # Backtrack
    
    result = []
    backtrack(0)
    return result

# Example usage
print(permute([1, 2, 3]))  # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(permute([0, 1]))     # [[0, 1], [1, 0]]
            

function permute(nums) {
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]]; // Backtrack
        }
    }
    
    let result = [];
    backtrack(0);
    return result;
}

// Example usage
console.log(permute([1, 2, 3])); // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
console.log(permute([0, 1]));    // [[0, 1], [1, 0]]
            

Explanation

• Base Case: When start equals the array length, add a copy of the current permutation.
• Recursive Step: Swap the current position with each subsequent element and recurse.
• Backtracking: Restore the array by swapping back after each recursive call.
• Flow Example (nums=[1,2]): [1,2] → recurse → [1,2]; swap to [2,1] → recurse → [2,1].
• Distinctness: Assumes input has no duplicates; adjust with a set if duplicates are present.

Note