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