Permutations II

Intuition

Use a DFS.

To avoid duplicate, we should use a counts and only use one value for one position once.

Solution


class Solution:
    def permuteUnique(self, nums):
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 0
            counts[num] += 1

        return self._dfs(counts)

    def _dfs(self, counts):
        if len(counts) == 0:
            return []
        if len(counts) == 1 and list(counts.values())[0] == 1:
            return [[list(counts.keys())[0]]]

        res = []
        for current in list(counts.keys()):
            counts[current] -= 1
            if counts[current] == 0:
                counts.pop(current)

            for child in self._dfs(counts):
                res.append(child + [current])

            if current not in counts:
                counts[current] = 0
            counts[current] += 1

        return res