> For the complete documentation index, see [llms.txt](https://1005281342.gitbook.io/code-porter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://1005281342.gitbook.io/code-porter/suan-fa/1_dfs.md).

# DFS

## 全排列问题

[46. 全排列](https://leetcode-cn.com/problems/permutations/)

```python
# https://leetcode-cn.com/problems/permutations/
from typing import List


class Solution:

    def __init__(self):
        self.nums = list()
        self.ans = list()
        self.path = list()
        self.st = list()

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.ans = list()
        self.st = [False] * len(nums)
        self.path = [0] * len(nums)

        self.dfs(0)
        return self.ans

    def dfs(self, u: int):
        if u == len(self.nums):
            # 进行拷贝
            self.ans.append(self.path[:])
            return
        for i in range(len(self.nums)):
            # 说明已经用过了
            if self.st[i]:
                continue

            # 选择
            self.path[u] = self.nums[i]
            self.st[i] = True
            self.dfs(u + 1)
            # 回溯
            self.st[i] = False
            # self.path[u] = 0  # 其实每次都会在在选择时被nums[i]覆盖，不恢复path[u]也可以
```

## N皇后问题

[51. N皇后](https://leetcode-cn.com/problems/n-queens/)

```python
# https://leetcode-cn.com/problems/n-queens/
from typing import List


class Solution:

    def __init__(self):
        self.n = 0
        self.x = list()  # 竖行
        self.dg = list()  # 左对角线: y = - x + b -> b = x + y
        self.udg = list()  # 右对角线: y = x + b -> b = y - x
        self.ans = list()
        self.path = list()

    def solveNQueens(self, n: int) -> List[List[str]]:
        self.n = n
        self.x = [False] * n * 2
        self.dg = [False] * n * 2
        self.udg = [False] * n * 2
        self.path = [['.'] * n for _ in range(n)]

        self.dfs(0)
        return self.ans

    def dfs(self, u):
        if u == self.n:
            self.ans.append(["".join(x) for x in self.path])
            return

        for i in range(self.n):
            if self.x[i] or self.dg[u + i] or self.udg[self.n + i - u]:
                continue
            self.path[u][i] = 'Q'
            self.x[i] = self.dg[u + i] = self.udg[self.n + i - u] = True
            self.dfs(u + 1)
            self.x[i] = self.dg[u + i] = self.udg[self.n + i - u] = False
            self.path[u][i] = '.'
```

**一种更原始的做法**

```python
# https://leetcode-cn.com/problems/n-queens/
from typing import List


class Solution:

    def __init__(self):
        self.n = 0
        self.x = list()  # 竖行
        self.y = list()  # 横行
        self.dg = list()  # 左对角线: y = - x + b -> b = x + y
        self.udg = list()  # 右对角线: y = x + b -> b = y - x
        self.ans = list()
        self.path = list()

    def solveNQueens(self, n: int) -> List[List[str]]:
        self.n = n
        self.x = [False] * n * 2
        self.y = [False] * n * 2
        self.dg = [False] * n * 2
        self.udg = [False] * n * 2
        self.path = [['.'] * n for _ in range(self.n)]

        self.dfs(0, 0, 0)  # 从（0，0）点开始搜索，皇后放置个数为0
        return self.ans

    def dfs(self, x, y, cnt):
        # 当前行已经走完，需要换行
        if y == self.n:
            y = 0
            x += 1

        # 已经遍历完
        if x == self.n:
            # 找到一种可行方案
            if cnt == self.n:
                self.ans.append(["".join(x) for x in self.path])
            return

        self.dfs(x, y + 1, cnt)

        if self.x[x] or self.y[y] or self.dg[y + x] or self.udg[self.n + y - x]:
            return

        self.path[x][y] = "Q"
        self.x[x] = self.y[y] = self.dg[y + x] = self.udg[self.n + y - x] = True
        self.dfs(x, y + 1, cnt + 1)
        self.x[x] = self.y[y] = self.dg[y + x] = self.udg[self.n + y - x] = False
        self.path[x][y] = "."
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://1005281342.gitbook.io/code-porter/suan-fa/1_dfs.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.