46. Permutations

Question

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution 1: DFS

class Solution:
    def __init__(self):
        self.ans = []
        
    def dfs(self, restPermu: List[int], prevPermu: List[int]) -> None:
        if not restPermu:
            self.ans.append(prevPermu)
        for i in range(len(restPermu)):
            self.dfs(restPermu[:i] + restPermu[i+1:], prevPermu + [restPermu[i]])
        
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.dfs(nums, [])
        return self.ans

Time Complexity: O(N!)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/permutations/discuss/18296/Simple-Python-solution-(DFS).
https://blog.csdn.net/Jacky_chenjp/article/details/66477538

Follow-up: 47. Permutations II

Follow-up: 60. Permutation Sequence

31. Next Permutation