Permutations

46. Permutations

Solution

dfs(nums = [1, 2, 3] , path = [] , result = [] )
|__ dfs(nums = [2, 3] , path = [1] , result = [] )
| |dfs(nums = [3] , path = [1, 2] , result = [] )
| | |dfs(nums = [] , path = [1, 2, 3] , result = [[1, 2, 3]] )
| |dfs(nums = [2] , path = [1, 3] , result = [[1, 2, 3]] )
| |dfs(nums = [] , path = [1, 3, 2] , result = [[1, 2, 3], [1, 3, 2]] )
|__ dfs(nums = [1, 3] , path = [2] , result = [[1, 2, 3], [1, 3, 2]] )
| |dfs(nums = [3] , path = [2, 1] , result = [[1, 2, 3], [1, 3, 2]] )
| | |__dfs(nums = [] , path = [2, 1, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] )
| |dfs(nums = [1] , path = [2, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] )
| |dfs(nums = [] , path = [2, 3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
|__ dfs(nums = [1, 2] , path = [3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
|dfs(nums = [2] , path = [3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
| |__dfs(nums = [] , path = [3, 1, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] )
|dfs(nums = [1] , path = [3, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] )
|__dfs(nums = [] , path = [3, 2, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] )

def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    L = len(nums)
    res = []
    def dfs(l, remaining, path):
        if l == L:
            res.append(path)
        for i, r in enumerate(remaining):
            dfs(l+1, remaining[:i] + remaining[i+1:], path + [r])
    dfs(0, nums, [])
    return res