Use a DFS to generate all permutations.
class Solution:
def permute(self, nums):
used = [False] * len(nums)
return self._dfs(nums, used)
def _dfs(self, nums, used):
if all(used):
return []
if used.count(False) == 1:
return [[nums[used.index(False)]]]
res = []
for i, j in enumerate(used):
if j:
continue
used[i] = True
for child in self._dfs(nums, used):
res.append(child + [nums[i]])
used[i] = False
return res