力扣00046.全排列

发表于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 7 分钟
全排列、数组、回溯、中等

题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }
private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, result);
            swap(nums[start], nums[i]);  // 回溯
        }
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 8.74 MB, 击败 20.97% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPermutation = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, currentPermutation, result);
        return result;
    }
    private void backtrack(int[] nums, boolean[] used, List<Integer> currentPermutation, List<List<Integer>> result) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.add(nums[i]);
                backtrack(nums, used, currentPermutation, result);
                currentPermutation.remove(currentPermutation.size() - 1);
                used[i] = false;
            }
        }
    }
}

结果

执行用时 : 1 ms, 击败 83.32% 使用 Java 的用户

内存消耗 : 43.70 MB, 击败 5.05% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        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]
        result = []
        backtrack(0)
        return result

结果

执行用时 : 18 ms, 击败 67.64% 使用 Python 的用户

内存消耗 : 11.63 MB, 击败 95.42% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        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]
        result = []
        backtrack(0)
        return result

结果

执行用时 : 43 ms, 击败 57.96% 使用 Python3 的用户

内存消耗 : 16.61 MB, 击败 38.86% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void backtrack(int *nums, int numsSize, int start, int ***result, int *resultSize, int **resultColumnSizes) {
    if (start == numsSize) {
        (*resultSize)++;
        *result = realloc(*result, sizeof(int *) * (*resultSize));
        (*result)[(*resultSize) - 1] = malloc(sizeof(int) * numsSize);
        for (int i = 0; i < numsSize; i++) {
            (*result)[(*resultSize) - 1][i] = nums[i];
        }
        (*resultColumnSizes) = realloc(*resultColumnSizes, sizeof(int) * (*resultSize));
        (*resultColumnSizes)[(*resultSize) - 1] = numsSize;
        return;
    }
    for (int i = start; i < numsSize; i++) {
        swap(&nums[start], &nums[i]);
        backtrack(nums, numsSize, start + 1, result, resultSize, resultColumnSizes);
        swap(&nums[start], &nums[i]);  // 回溯
    }
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int **result = NULL;
    *returnSize = 0;
    *returnColumnSizes = NULL;
    backtrack(nums, numsSize, 0, &result, returnSize, returnColumnSizes);
    return result;
}

结果

执行用时 : 4 ms, 击败 99.53% 使用 C 的用户

内存消耗 : 15.20 MB, 击败 5.08% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        List<IList<int>> result = new List<IList<int>>();
        List<int> currentPermutation = new List<int>();
        bool[] used = new bool[nums.Length];
        Backtrack(nums, used, currentPermutation, result);
        return result;
    }
    private void Backtrack(int[] nums, bool[] used, List<int> currentPermutation, List<IList<int>> result) {
        if (currentPermutation.Count == nums.Length) {
            result.Add(new List<int>(currentPermutation));
            return;
        }
        for (int i = 0; i < nums.Length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.Add(nums[i]);
                Backtrack(nums, used, currentPermutation, result);
                currentPermutation.RemoveAt(currentPermutation.Count - 1);
                used[i] = false;
            }
        }
    }
}

结果

执行用时 : 111 ms, 击败 55.73% 使用 C# 的用户

内存消耗 : 46.11 MB, 击败 17.71% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let result = [];
    let currentPermutation = [];
    let used = new Array(nums.length).fill(false);
    const backtrack = (start) => {
        if (start === nums.length) {
            result.push([...currentPermutation]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.push(nums[i]);
                backtrack(start + 1);
                currentPermutation.pop();
                used[i] = false;
            }
        }
    };
    backtrack(0);
    return result;
};

结果

执行用时 : 67 ms, 击败 88.42% 使用 JavaScript 的用户

内存消耗 : 53.24 MB, 击败 6.32% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const currentPermutation: number[] = [];
    const used: boolean[] = new Array(nums.length).fill(false);
    const backtrack = (start: number): void => {
        if (start === nums.length) {
            result.push([...currentPermutation]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.push(nums[i]);
                backtrack(start + 1);
                currentPermutation.pop();
                used[i] = false;
            }
        }
    };
    backtrack(0);
    return result;
}

结果

执行用时 : 76 ms, 击败 74.55% 使用 TypeScript 的用户

内存消耗 : 53.70 MB, 击败 20.45% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        $result = [];
        $currentPermutation = [];
        $used = array_fill(0, count($nums), false);
        $this->backtrack($nums, $used, $currentPermutation, $result);
        return $result;
    }
    private function backtrack($nums, &$used, &$currentPermutation, &$result) {
        if (count($currentPermutation) === count($nums)) {
            $result[] = $currentPermutation;
            return;
        }
        for ($i = 0; $i < count($nums); $i++) {
            if (!$used[$i]) {
                $used[$i] = true;
                $currentPermutation[] = $nums[$i];
                $this->backtrack($nums, $used, $currentPermutation, $result);
                array_pop($currentPermutation);
                $used[$i] = false;
            }
        }
    }
}

结果

执行用时 : 14 ms, 击败 14.29% 使用 PHP 的用户

内存消耗 : 20.39 MB, 击败 19.05% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var currentPermutation: [Int] = []
        var used: [Bool] = Array(repeating: false, count: nums.count)
        backtrack(nums, &used, &currentPermutation, &result)
        return result
    }
    private func backtrack(_ nums: [Int], _ used: inout [Bool], _ currentPermutation: inout [Int], _ result: inout [[Int]]) {
        if currentPermutation.count == nums.count {
            result.append(currentPermutation)
            return
        }
        for i in 0..<nums.count {
            if !used[i] {
                used[i] = true
                currentPermutation.append(nums[i])
                backtrack(nums, &used, &currentPermutation, &result)
                currentPermutation.removeLast()
                used[i] = false
            }
        }
    }
}

结果

执行用时 : 15 ms, 击败 8.55% 使用 Swift 的用户

内存消耗 : 15.90 MB, 击败 5.13% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result: MutableList<MutableList<Int>> = mutableListOf()
        val currentPermutation: MutableList<Int> = mutableListOf()
        val used: BooleanArray = BooleanArray(nums.size)
        backtrack(nums, used, currentPermutation, result)
        return result
    }
    private fun backtrack(nums: IntArray, used: BooleanArray, currentPermutation: MutableList<Int>, result: MutableList<MutableList<Int>>) {
        if (currentPermutation.size == nums.size) {
            result.add(ArrayList(currentPermutation))
            return
        }
        for (i in nums.indices) {
            if (!used[i]) {
                used[i] = true
                currentPermutation.add(nums[i])
                backtrack(nums, used, currentPermutation, result)
                currentPermutation.removeAt(currentPermutation.size - 1)
                used[i] = false
            }
        }
    }
}

结果

执行用时 : 172 ms, 击败 98.86% 使用 Kotlin 的用户

内存消耗 : 36.45 MB, 击败 96.59% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  List<List<int>> permute(List<int> nums) {
    List<List<int>> result = [];
    List<int> currentPermutation = [];
    List<bool> used = List.filled(nums.length, false);
    void backtrack() {
      if (currentPermutation.length == nums.length) {
        result.add(List.from(currentPermutation));
        return;
      }
      for (int i = 0; i < nums.length; i++) {
        if (!used[i]) {
          used[i] = true;
          currentPermutation.add(nums[i]);
          backtrack();
          currentPermutation.removeLast();
          used[i] = false;
        }
      }
    }
    backtrack();
    return result;
  }
}

结果

执行用时 : 281 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 143.52 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func permute(nums []int) [][]int {
	result := [][]int{}
	currentPermutation := []int{}
	used := make([]bool, len(nums))
	var backtrack func()
	backtrack = func() {
		if len(currentPermutation) == len(nums) {
			temp := make([]int, len(nums))
			copy(temp, currentPermutation)
			result = append(result, temp)
			return
		}
		for i := 0; i < len(nums); i++ {
			if !used[i] {
				used[i] = true
				currentPermutation = append(currentPermutation, nums[i])
				backtrack()
				currentPermutation = currentPermutation[:len(currentPermutation)-1]
				used[i] = false
			}
		}
	}
	backtrack()
	return result
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.48 MB, 击败 88.20% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
  result = []
  current_permutation = []
  used = Array.new(nums.length, false)
  backtrack = lambda do
    if current_permutation.length == nums.length
      result << current_permutation.dup
      return
    end
    nums.each_with_index do |num, i|
      next if used[i]
      used[i] = true
      current_permutation << num
      backtrack.call
      current_permutation.pop
      used[i] = false
    end
  end
  backtrack.call
  result
end

结果

执行用时 : 83 ms, 击败 22.22% 使用 Ruby 的用户

内存消耗 : 206.71 MB, 击败 11.11% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
object Solution {
  def permute(nums: Array[Int]): List[List[Int]] = {
    var result: List[List[Int]] = List()
    var currentPermutation: List[Int] = List()
    var used: Array[Boolean] = Array.fill[Boolean](nums.length)(false)
    def backtrack(): Unit = {
      if (currentPermutation.length == nums.length) {
        result = result :+ currentPermutation
        return
      }
      for (i <- nums.indices) {
        if (!used(i)) {
          used(i) = true
          currentPermutation = currentPermutation :+ nums(i)
          backtrack()
          currentPermutation = currentPermutation.init
          used(i) = false
        }
      }
    }
    backtrack()
    result
  }
}

结果

执行用时 : 516 ms, 击败 66.67% 使用 Scala 的用户

内存消耗 : 57.46 MB, 击败 16.67% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
impl Solution {
    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut current_permutation = Vec::new();
        let mut used = vec![false; nums.len()];
        fn backtrack(
            nums: &Vec<i32>,
            used: &mut Vec<bool>,
            current_permutation: &mut Vec<i32>,
            result: &mut Vec<Vec<i32>>,
        ) {
            if current_permutation.len() == nums.len() {
                result.push(current_permutation.clone());
                return;
            }
            for i in 0..nums.len() {
                if !used[i] {
                    used[i] = true;
                    current_permutation.push(nums[i]);
                    backtrack(nums, used, current_permutation, result);
                    current_permutation.pop();
                    used[i] = false;
                }
            }
        }
        backtrack(&nums, &mut used, &mut current_permutation, &mut result);
        result
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.11 MB, 击败 61.80% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

1
2
3
4
5
6
7
8
9
10
11
-spec permute([integer()]) -> [[integer()]].
permute(Nums) ->
    backtrack(Nums, []).
backtrack([], Perms) ->
    [Perms];
backtrack(Nums, Perms) ->
    lists:flatmap(fun(Elem) ->
        NewPerms = Perms ++ [Elem],
        NewNums = lists:delete(Elem, Nums),
        backtrack(NewNums, NewPerms)
    end, Nums).

结果

执行用时 : 203 ms, 击败 100.00% 使用 Erlang 的用户

内存消耗 : 55.70 MB, 击败 100.00% 使用 Erlang 的用户

Elixir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
defmodule Solution do
  @spec permute(nums :: [integer]) :: [[integer]]
  def permute(nums) do
    backtrack(nums, [])
  end
  defp backtrack([], perms) do
    [perms]
  end
  defp backtrack(nums, perms) do
    Enum.flat_map(nums, fn elem ->
      new_perms = perms ++ [elem]
      new_nums = Enum.filter(nums, &(&1 != elem))
      backtrack(new_nums, new_perms)
    end)
  end
end

结果

执行用时 : 281 ms, 击败 -% 使用 Elixir 的用户

内存消耗 : 68.01 MB, 击败 100.00% 使用 Elixir 的用户