全排列

Leetcode Link: 46. 全排列 - 力扣（LeetCode）

题目

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

解法一

思路：回溯的排列问题，排列问题不同于子集问题，同样的元素组成，不同的顺序，算两个结果。

显然本题收集的是叶子节点

满足题目的条件：

1. 走到了叶子节点，即 nums 中所有的数字全都用了 len(path)==len(nums)

停止回溯的条件：

1. 同上，没有特殊情况需要停止回溯

剪枝：

1. 遇到已经用过的数字的时候，需要跳过，即不能val in path==True

本题特殊在输入 nums 中的数字都是不一样的，加上本题属于排列问题，那么每层的 choose 实际上就是 nums 自己。 但是需要注意的是已经用过的数字(即在path中的数字)不能重复使用

题解：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtracking():
            nonlocal nums, res, path
            # 满足条件，收集叶节点，停止递归
            if len(path) == len(nums):
                res.append(copy.deepcopy(path))
                return
            
            # 本题其每次的choose就是nums自己
            for val in nums:
                # 本题中 nums 无重复数字，那么就要保证path中别重复用一个数字
                if val not in path:
                    path.append(val)
                    backtracking()
                    path.pop()
                else:
                    continue
        res = []
        path = []
        backtracking()
        return res
 

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系