组合问题

  1. 什么时候需要用startIndex？

如果是一个集合来求组合的话，就需要startIndex，例如：77.组合(opens new window)，216.组合总和III(opens new window)。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组

  1. 元素可以重复选取怎么处理？

在回溯的时候不用 i+1

  1. for (int i = startIndex; i < candidates.size(); i++) {
  2.     sum += candidates[i];
  3.     path.push_back(candidates[i]);
  4.     backtracking(candidates, target, sum, i); // 关键点:不用i+1了，表示可以重复读取当前的数
  5.     sum -= candidates[i];   // 回溯
  6.     path.pop_back();        // 回溯
  7. }

  1. 在求和问题中，排序之后加剪枝是常见的套路！

  2. 数组candidates的元素是有重复的怎么办？

树层去重：需要对数组排序

分割问题

本质上也是组合问题

子集问题

和组合问题和分割问题的区别在于，既要记录叶子节点，也要记录树的中间节点——也就是每次都记录

  1. candidates数组中包含了重复元素怎么办？

同组合问题，要树层去重(需要对数组排序)

  1. *递增子序列问题，由于不能对candidates数组排序，因此之前的去重方法不能用，如何处理？

每一层都新开一个used 的HashMap，用来记录这次横向遍历中是否存在重复选取的情况，因此也不需要回滚

排列问题

  1. 排列问题与组合问题的不同之处：
  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了
  1. candidates数组中包含了重复元素怎么办？

同组合问题，要树层去重(需要对数组排序).对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！