Leetcode-46-全排列

# Leetcode-46-全排列

# 题目说明

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

示例 1：

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

1
2

示例 2：

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

1
2

示例 3：

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

1
2

提示：

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

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/permutations

# 题解

回溯法+剪枝

def backtracking(nums, result, used, permutation):
    if len(nums) == len(permutation):
        result.append(permutation.copy())
        return
    for i in range(0, len(nums)):
        if used[i] == False:
            permutation.append(nums[i])
            used[i] = True
            backtracking(nums, result, used, permutation)
            used[i] = False
            permutation.pop()


def fun(nums):
    result = []
    used = dict()
    for i in range(0, len(nums)):
        used[i] = False
    backtracking(nums, result, used, [])
    return result

print(fun([1,2,3,4]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

编辑

#回溯法

上次更新: 2023/02/16, 22:15:06

← 动态规划算法 Leetcode-78-子集→