Permutations

Problem Id: 46 Difficulty: Medium Tag: Backtracking


Intuition

Use a DFS to generate all permutations.

Solution


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