RE_回溯1
需积分: 0 145 浏览量
2022-08-03
20:35:46
上传
评论
收藏 245KB PDF 举报
RE_回溯.md
2021/6/22
1 / 5
Q31 : 下一个排列
1. 654321 ： 是最大排列
2. 146532 ： 是 14 开头的最大排列， 此时递增只能用6532中大于4的最小元素5开始 ： 15开头
3. 而15开头的最小字典序为 15 2346 . 即交换大于4的最小元素5与4的位置，然后后边构成递减序列，逆置
该递减序列，即为最小字典序。
39 : 组合总和 无重复数组，数字可以重复选取，拼target, 结果不可重复。
0. 两种写法，对应两种递归树结构。2,3,6,7
1. 对 cur 在cur层，直接对cur选多次(包括0次) ，第一层就是分为 对第一个数，选择次数的不同，归为不同
分支。 第二层就是在选择第一个数的基础上，选择第二个数次数的不同，分为不同分支。按照cur的不同
选择次数划分分支。
root
'' 2 22 222 选2
'' 3 33 23 223 选3 '' 3 选6 ''7 选7
2. begin写法。规则是，第一层是从 0到end选不同的数，分不同的枝。
root
2 3 6 7 root从0开始选
22 23 3 6
223 23
每个节点向下一个结点发展时， 他上次选择的最后一个位置就是下次选择的起始位置。
3. 这题两种写法都好实现，且复杂度一样、
Q40 : 组合总和 II : 有重复元素数组， 每个数字只能选一次， 拼target, 结
果不可重复。
1. 每个元素分为选或者不选进行分支。 一层只指针cur一个元素，分两支。如果有两个2. 选第一个不选第二
个， 和不选第一个选第二个 形成了重复。 这样就很难去重。选和不选其实就是上边的 选0次和选多次，
不过这题规定最多一次。
改进：避免重复：如果我们按顺序对每一个元素，使用选或者不选的策略，那么一定会有重
复。
改变车略，我们将 相同的数，改为，选0次，选1次，选多次，
可以先使用一个map统计 记录其最后一个的下标位置。
int = cur;
for(; i <= map.get(num[cur]); i++){
dfs(map.get(num[cur])+1, sum += num[cur]*(i-cur+1))
评论0