ref.md

• Next Permutation

  STL风格版本，利用reverse_iterator简化边界判断，可处理重复元素。参见：生成全排列、下一个排列、第k个排列的。

• Unique Binary Search Trees

  一维DP版本，时间复杂度O(N^2)，空间复杂度O(N)

• Recover Binary Search Tree

  基本思想是中序遍历二叉树，寻找逆序数对。

  • 简单版本，空间复杂度O(N)

  • Morris Traversal版本，空间复杂度O(1)

    参见Binary Tree Inorder Traversal（题目、Morris Traversal参考实现）

• Subsets

  令集合大小为N，常见子集生成思路：

  • 遍历长度为N的Gray Codes（相关LeetCode题目、Wikipedia条目）
  • 遍历0至2^N - 1的所有整数

  以上两个思路都是每个整数对应于一个子集，其中第i个bit代表原集合中第i个元素是否存在于目标子集。缺点在于N较大时需要用到大整数运算。给出的参考实现不存在这个缺点，思路类似于Gray Code遍历（将j由递增改为递减便成为Gray Code顺序）。