题解 | 没有重复项数字的全排列

简要思想:

将当前的num排序 (python的sorted支持对list排序), 然后从num第一个数开始遍历到最后一个数.

对每个数字将其当作头部, 剩余数字组成下次递归的数组, 递归后得到排序后的所有全排列尾部, 之后将头部和每个全排列尾部拼接, 就是当前num的一个全排列.

class Solution:
    def permute(self, num: List[int]) -> List[List[int]]:
        # write code here
        if len(num) == 1:
            return [num]
        ret = []
        tmp_nums = sorted(num)
        for i in range(len(tmp_nums)):
            head = tmp_nums[i]
            tail = tmp_nums[:i] + tmp_nums[i + 1 :]
            # print(tail)
            permuted_tails = self.permute(tail)
            for permuted_tail in permuted_tails:
                ret.append([head] + permuted_tail)
        return ret