没有重复项数字的全排列

没有重复项数字的全排列_牛客题霸_牛客网

问题简述

给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

思路：DFS+回溯

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        
        ret = []
        tmp = []
        N = len(num)
        book = [0] * N
        
        def dfs(deep):
            if deep == N:
                ret.append(tmp[:])
            
            for i in range(N):
                if book[i]:
                    continue
                
                book[i] = 1
                tmp.append(num[i])
                dfs(deep + 1)
                tmp.pop()
                book[i] = 0
        
        dfs(0)
        return ret