[LC] 0046 Permutations

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/permutations/">Permutations</a>
 * 数组；回溯
 */
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }

        backtrack(0, nums.length, output, res);
        return res;
    }

    private void backtrack(int cur, int n, List<Integer> output, List<List<Integer>> res) {
        if (cur == n) {   // 所有数都填完了
            res.add(new ArrayList<>(output));
        }

        for (int i = cur; i < n; i++) {
            Collections.swap(output, cur, i); // 动态维护数组
            backtrack(cur + 1, n, output, res);   // 继续递归填下一个数
            Collections.swap(output, cur, i); // 撤销操作
        }
    }
}

Go

func permute(nums []int) (res [][]int) {
    output := make([]int, len(nums))
    for i := range nums {
        output[i] = nums[i]
    }

    var backtrack func(int, int, []int, *[][]int)
    backtrack = func(cur int, n int, output []int, res *[][]int) {
        if cur == n {
            *res = append(*res, append([]int{}, output...))
        }

        for i := cur; i < n; i++ {
            output[cur], output[i] = output[i], output[cur]
            backtrack(cur+1, n, output, res)
            output[cur], output[i] = output[i], output[cur]
        }
    }

    backtrack(0, len(nums), output, &res)
    return res
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    let res = [];
    let output = [];
    for (let num of nums) {
        output.push(num);
    }

    const backtrack = (cur, n, output, res) => {
        if (cur === n) {
            res.push([...output]);
            return;
        }

        for (let i = cur; i < n; i++) {
            [output[cur], output[i]] = [output[i], output[cur]];
            backtrack(cur + 1, n, output, res);
            [output[cur], output[i]] = [output[i], output[cur]];
        }
    };

    backtrack(0, nums.length, output, res);
    return res;
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute(array $nums): array {
        $res = [];
        $output = $nums;
        $this->backtrack(0, count($nums), $output, $res);
        return $res;
    }

    private function backtrack(int $cur, int $n, array &$output, array &$res): void {
        if ($cur == $n) {
            $res[] = $output;
            return;
        }

        for ($i = $cur; $i < $n; $i++) {
            [$output[$cur], $output[$i]] = [$output[$i], $output[$cur]];
            $this->backtrack($cur + 1, $n, $output, $res);
            [$output[$cur], $output[$i]] = [$output[$i], $output[$cur]];
        }
    }
}