class Solution(object):

    def permute(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        n = len(nums)

        results = []

        def backtrack(first = 0):

            if first == n:

                results.append(nums[:])

                return

            for i in range(first, n):

                nums[first], nums[i] = nums[i], nums[first]

                backtrack(first + 1)

                nums[first], nums[i] = nums[i], nums[first]

        backtrack()

        return results

class Solution(object):

    def permuteUnique(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        n = len(nums)

        results = []

        def backtrack(first = 0):

            if first == n:

                results.append(nums[:])

                return

            s = set()

            for i in range(first, n):

                if nums[i] in s:

                    continue

                s.add(nums[i])

                nums[first], nums[i] = nums[i], nums[first]

                backtrack(first + 1)

                nums[first], nums[i] = nums[i], nums[first]

        backtrack()

        return results

class Solution(object):

    def solveNQueens(self, n):

        """

        :type n: int

        :rtype: List[List[str]]

        """

        results = []

        result = ["." * n] * n

        l = set()

        c = set()

        x = set()

        y = set()

        def backtrack(first=0):

            if first == n:

                results.append(result[:])

                return

            for i in range(n):

                if i in l or first in c or i - first in x or i + first in y:

                    continue

                l.add(i), c.add(first), x.add(i - first), y.add(i + first)

                result[i] = first * "." + "Q" + (n - first - 1) * "."

                backtrack(first + 1)

                l.remove(i), c.remove(first), x.remove(i - first), y.remove(i + first)

                result[i] = n * "."

        backtrack()

        return results

class Solution(object):

    def totalNQueens(self, n):

        """

        :type n: int

        :rtype: int

        """

        self.results = 0

        l = set()

        c = set()

        x = set()

        y = set()

        def backtrack(first=0):

            if first == n:

                self.results += 1

                return

            for i in range(n):

                if i in l or first in c or i - first in x or i + first in y:

                    continue

                l.add(i), c.add(first), x.add(i - first), y.add(i + first)

                backtrack(first + 1)

                l.remove(i), c.remove(first), x.remove(i - first), y.remove(i + first)

        backtrack()

        return self.results