46. Permutations

Problem

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

A permutation is a rearrangement of all the elements of an array.

https://leetcode.cn/problems/permutations/

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]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Test Cases

1 2	class Solution: def permute(self, nums: List[int]) -> List[List[int]]:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([1,2,3], [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
    ([0,1], [[0,1],[1,0]]),
    ([1], [[1]]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    assert sorted(sol.permute(nums)) == sorted(expected)

Thoughts

用回溯法。

排列的第一个数字有 n 种选择，第二个数字有 n - 1 种选择，……。一共有 n! 种不同的排列。

时间复杂度 O(n!)，额外的空间复杂度 O(n²)（因为目前的实现，每一层递归需要用 O(n) 辅助空间。

也可以只用 O(n) 辅助空间，记录每个数字是否已经用在当前排列，而时间复杂度为 O(nⁿ)。

Code

solution.py

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []

        def backtrack():
            if not remains:
                result.append(path.copy())
                return

            for num in list(remains):
                path.append(num)
                remains.remove(num)
                backtrack()
                path.pop()
                remains.add(num)

        path = []
        remains = set(nums)
        backtrack()
        return result

反向引用
- 47. Permutations II

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。