回溯算法回顾

回溯算法回顾

1.如果是一个集合来求组合的话，就需要startIndex，例如：回溯算法：求组合问题！?(opens new window)，回溯算法：求组合总和！?(opens new window)；如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：回溯算法：电话号码的字母组合

?2.去重操作，采用used数组对于元素是否取用进行标记，注意要对数组中的元素进行排序，有两种去重，树层去重和树枝去重，如果查询used[i]==true则同枝使用，used[i]==false树层已用。

3.切割问题：

• 切割问题其实类似组合问题
• 如何模拟那些切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串
• 如何判断回文

4.?子集问题，在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

5.排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。