递增子序列
题解:
乍一看这道题,好像是需要把原数组要排序的,其实不需要,我们通过两个示例就可以看出,他是找这序列中的递增子序列的
我们通过例子4,5,4,5],先取4 余[5, 4, 5],再取5,因为5>4,放入符合的path中,余[4, 5], 再取4, 4 < path[-1],回溯,再取5, 5 == path[-1],满足条件,放入path中,。。。还要考虑去重
1.递归方法的参数
题目中给定的nums,以及start_index
2.终止条件
不需要终止条件,满足至少有两个元素的情况,if len(path) > 1: result.append(path[:])
3.单层搜索逻辑
正如我在前面解释的
代码:
全排列
题解
1. 递归方法的参数
全排列和组合的不同之处在于,排列是有序的,就是说【1,2】和【2,1】是两个集合,因此,不能使用start_index了,但是需要一个used数组,需要标记已经选择的元素
2,终止条件
收集元素数组的长度和nums数组的长度一致的时候,说明找到了一个全排列
3.单层搜索逻辑
因为排列问题,每次都要从头开始遍历,而used数组,其实记录此时path中都有哪些元素使用了,一个排列里一个元素只能使用一次
代码:
全排列ii
题解:
此题需要去重的操作,按照之前的组合方法去重即可,切记,需要对原数组进行排序
代码: