提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

今天第一题答案全写题目上了，于是又写了第二题QAQ好难，以后再也不这么干了
感觉dfs还是不太熟练，稍微变一下就很容易出错，
比如回溯的时机（调用函数后，for循环内部）；
比如二维列表的append（）操作（传入切片，别传引用）；
比如兄弟节点剪枝的时机（要在回溯之后剪枝，就像先从子节点回到父节点，再选择要不要到兄弟节点）

一、题目

外观数列

给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列：countAndSay(1) = “1”，countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
1
2
3
4
5

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 “3322251” 的描述如下图：

示例

示例 1：
输入：n = 1
输出：“1”
解释：这是一个基本样例。

示例 2：
输入：n = 4
输出：“1211”
解释：
countAndSay(1) = “1”
countAndSay(2) = 读 “1” = 一 个 1 = “11”
countAndSay(3) = 读 “11” = 二 个 1 = “21”
countAndSay(4) = 读 “21” = 一 个 2 + 一 个 1 = “12” + “11” = “1211”

提示

1 <= n <= 30

二、思路

本题就是求数列的第n项，因为数列中每一个元素由其前元素决定，因此只需要将求元素的递推方法迭代循环n次即可（此处采用while循环）
而递推方法题目上已经说的很明确，在此不在赘述：
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

三、代码

1.python

class Solution:
    def countAndSay(self, n: int) -> str:
        x=1 
        s='1' #第一项
        while(x<n):
            count=0 #在循环中记录s当前的连续最多相同字符数目
            r='' #本轮生成的第x项
            for i in range(len(s)): #遍历数组
                if(i==0 or s[i]!=s[i-1]): #字符不连续了
                    if(count!=0): #记录一下
                        r=r+str(count)+str(s[i-1])
                    count=1#记录第一个元素
                else:
                    count+=1
            if(count!=0):#记录最后一组元素
                r=r+str(count)+str(s[-1])
            s=r #更新s值
            x+=1 #更新x值
        return s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

四、题目

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []

提示

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都 互不相同
1 <= target <= 500

五、思路

看到组合题，一定可以用搜索回溯算法解决，此时的关键就是画出一棵表示所有情况的树来帮助形成剪枝策略，就以[2,3,6,7],7为例：

由上图可以看出，若先将candidates整理为升序
①为了去重，每层应只对父节点元素及其后元素进行分支，这样才能保证结果中没有降序序列
②如果某结点分支中有一个恰好等于或大于target，其后分支无需再检验，一定大于target
这样就可以开始写代码了
注意：
(1)回溯的代码在for循环内，因为兄弟节点间也需要回溯，事实上，如果被更改的参数是不可变类型，在传入参数时更改可以免于回溯（如sum），而若是引用类型（如re_part），则一定要回溯的。
(2)数组的增删全靠返回时的pop（即回溯），并不需要人为对数组清零或更改
(3)python不允许用户在函数的参数传递中选择是值传递还是引用传递，而是采用的对象引用传递，如果函数收到的是一个可变对象(如列表或字典)的引用，就采用引用传递。而如果收到的是一个不可变对象（如数字，字符和元组等）的引用，就采用值传递。在函数中将无法改变参数的原始值。递归函数只需传值即可，引用在递归函数外部定义，效果一样。
(4)这种生成的列表二维，更改其部分元素，会影响整个表。如果不想表被更改，需要用切片的方法复制一下子表，再添加到大表中：

l1.append(l2[:])
1

六、代码

python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort() #排序
        n=len(candidates) #数组长度
        re_list=[] #结果数组
        re_part=[] #部分数组
        def dfs(ssum,index,n): #当前和、上一轮的元素下标 
            if(ssum==target):
                re_list.append(re_part[:])
                return 1 #此后不必再循环（剪枝②）
            if(ssum>target):
                return 1 
            for i in range(index,n):
                re_part.append(candidates[i]) #元素加入部分数组
                flag=dfs(ssum+candidates[i],i,n) #下一层
                re_part.pop() #回溯到父节点
                if(flag==1): #如果上面一个孩子成功了或超界了，不用干了
                    break        
        #调用
        dfs(0,0,n)
        #返回
        return re_list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22