排列问题不需要startIndex
,因为不同的顺序代表了不同的结果,1,3,2
和1,2,3
是两种情况,这也是排列和组合的区别
组合问题中的切割问题,是通过不断移动切割的位置来考虑。切割线不断移动,得到不同的结果。 子集问题其实就是组合问题(无序性),
for
循环需要startIndex
而排列问题是有序的,则
for
循坏需要每次都从0
开始
DANGER
去重问题需要提前排序!
递归的时候用不用担心无限递归的情况?
保证传入的参数为i+1
,就不会出现无限递归的情况,因为i在for
循环里有限制条件。
如果要求递增的子序列,那就不能对原数据进行排序了,如果同时还需要去重的话,那就不能使用当前元素跟上一个元素比较了,因为元素是无序的,所以要用set
来唯一表示,且在每一层回溯前要进行初始化,因为每一层的去重情况都应重新考虑,层之间是互不影响的。
整颗树的同一层是否重复出现元素是我们控制不了的(这颗树本来就是抽象出来的),所以子集问题才会通过排序之后,判断相邻两个分支(nums[i] == nums[i - 1]
)的同一层是否同时出现元素来达到去重的目的