Permutations

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> out;
        function<void(int)> dfs = [&](int d){
            if (d == (int)nums.size()) { out.push_back(nums); return; }
            for (int i = d; i < (int)nums.size(); ++i) {
                swap(nums[d], nums[i]);
                dfs(d + 1);
                swap(nums[d], nums[i]);
            }
        };
        dfs(0);
        return out;
    }
};

func permute(nums []int) [][]int {
    out := [][]int{}
    var dfs func(d int)
    dfs = func(d int) {
        if d == len(nums) {
            tmp := make([]int, len(nums))
            copy(tmp, nums)
            out = append(out, tmp)
            return
        }
        for i := d; i < len(nums); i++ {
            nums[d], nums[i] = nums[i], nums[d]
            dfs(d + 1)
            nums[d], nums[i] = nums[i], nums[d]
        }
    }
    dfs(0)
    return out
}

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        out: List[List[int]] = []
        n = len(nums)

        def dfs(d: int) -> None:
            if d == n:
                out.append(nums[:])
                return
            for i in range(d, n):
                nums[d], nums[i] = nums[i], nums[d]
                dfs(d + 1)
                nums[d], nums[i] = nums[i], nums[d]

        dfs(0)
        return out

function permute(nums) {
    const out = [];
    const n = nums.length;
    const dfs = (d) => {
        if (d === n) {
            out.push(nums.slice());
            return;
        }
        for (let i = d; i < n; i++) {
            [nums[d], nums[i]] = [nums[i], nums[d]];
            dfs(d + 1);
            [nums[d], nums[i]] = [nums[i], nums[d]];
        }
    };
    dfs(0);
    return out;
}

class Solution {
    private int[] nums;
    private List<List<Integer>> out = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        dfs(0);
        return out;
    }

    private void dfs(int d) {
        if (d == nums.length) {
            List<Integer> tmp = new ArrayList<>(nums.length);
            for (int x : nums) tmp.add(x);
            out.add(tmp);
            return;
        }
        for (int i = d; i < nums.length; i++) {
            int t = nums[d]; nums[d] = nums[i]; nums[i] = t;
            dfs(d + 1);
            t = nums[d]; nums[d] = nums[i]; nums[i] = t;
        }
    }
}

function permute(nums: number[]): number[][] {
    const out: number[][] = [];
    const n = nums.length;
    const dfs = (d: number): void => {
        if (d === n) {
            out.push(nums.slice());
            return;
        }
        for (let i = d; i < n; i++) {
            [nums[d], nums[i]] = [nums[i], nums[d]];
            dfs(d + 1);
            [nums[d], nums[i]] = [nums[i], nums[d]];
        }
    };
    dfs(0);
    return out;
}