东营刚刚发生_上海市装修公司_杭州网络推广_谷歌seo公司

一、46. 全排列

• 思路：
  排列个数等于数据长度的阶乘，
• 代码：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)ans = []path = [0] * n     # 所有排列的长度都是一样的 ndef dfs (i, s):    # 从答案的角度，第i个位置该从s中选择哪一个。if i==n:ans.append(path.copy())returnfor x in s:path[i] = xdfs(i+1,  s-{x})dfs(0, set(nums))return ans

• 回溯的时间复杂度就是 路径长度*叶子节点 个数，这道题 $n!$ 个叶子节点，每个叶子节点个数为$n!$。

二、51. N 皇后

• 代码：

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:ans = []col = [0] * ndef valid(r, c):for R in range(r):C = col[R]if C == c or r+c == R+C or r-c == R-C:return Falsereturn Truedef dfs(r,s):if r==n:ans.append(["."*c + "Q" + "."*(n-1-c) for c in col])returnfor c in s:if valid(r, c):col[r] = cdfs(r+1, s-{c})dfs(0, set(range(n)))return ans