# 回溯总结

## 经典格式：

例如78题

```python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        for i in range(len(nums)+1):  #len+1轮循环，每次输出长度为i的所有组合
            self.backtrack(nums, tmpList, i, 0)
        return self.res

    def backtrack(self, nums, tmpList, k, start):
        if len(tmpList) == k:
            self.res.append(list(tmpList))
        else:
            for i in range(start, len(nums)):
                #经典回溯格式
                tmpList.append(nums[i])
                self.backtrack(nums, tmpList, k, i + 1)
                tmpList.pop()
```

### 简化

上面的递归操作**实质**上是将本层tmpList修改后传入下一层递归，待递归完成后再将tmpList还原。这波操作可以简化为直接在下一层**递归函数的参数**中对tmpList修改，这样本层递归的tmpList其实是不变的，即不能对tmpList做**直接操作**。

```python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        for i in range(len(nums)+1):  #len+1轮循环，每次输出长度为i的所有组合
            self.backtrack(nums, tmpList, i, 0)
        return self.res

    def backtrack(self, nums, tmpList, k, start):
        if len(tmpList) == k:
            self.res.append(list(tmpList))
        else:
            for i in range(start, len(nums)):    
                #tmp的修改直接写在递归里
                self.backtrack(nums, tmpList+[nums[i]], k, i + 1)
```

例如，若15行写作

```python
self.backtrack(nums, tmpList.append([nums[i]]), k, i + 1)
```

则报错，因为调用append函数对tmpList本身做了修改操作。回溯时本层的tmpList无法回复之前的状态

### 再简化

```python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        # 方法内定义回溯
        def backtrack(tmp, start, k):
            if len(tmp) == k:
                self.res.append(list(tmp))
            for i in range(start, len(nums)):
                backtrack(tmp+[nums[i]], i+1, k)
        
        for i in range(len(nums)+1):
            backtrack([], 0, i)  #递归
        return self.res
```

## 题目列表：

**22.括号生成**

**36.有效的数独**

**37.解数独**

**39.组合总和**

**40.组合总和Ⅱ**

**46.全排列**

**47.全排列Ⅱ**

**77.组合**

**78.子集**

**90.子集Ⅱ**


---

# Agent Instructions: 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:

```
GET https://cai-sen-se.gitbook.io/leetcode/hui-su-zong-jie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.