1、46题，全排列
https://leetcode-cn.com/problems/permutations/
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
2、47题，全排列二
https://leetcode-cn.com/problems/permutations-ii/
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
3、51题，N皇后
https://leetcode-cn.com/problems/n-queens/
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
4、52题，N皇后二
https://leetcode-cn.com/problems/n-queens-ii/
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