Permutation and Combination

• 基本题，但是非常重要，把这些题目做熟是必须的。

• 基本上来说，这类题的解法都是 DFS，程序的大体框架非常类似，只是根据题目的要求代码稍作修改。当然每道题也有不同的解法，但是你应该根据自己的喜好把这类题目的解决方案统一化。熟悉了这类题目以后对于 DFS 的理解会非常深刻。基本上一般的 DFS 的题目应该没什么问题了。

• 无论是排列还是组合，这类题都有一个变形，就是要求不能有重复的输出。PIE 和 CC150

  都没有提到相应的解法，大家应该很好的体会一下。如果没有相应的准备，属于面试的

  时候比较容易跪的题目。

(1) 基本类型

lc78 & lc90: Subsets I, II

lc77: Combinations

lc46: Permutation I, II

lc39, lc40, lc 216, lc377: Combination Combination Sum I, II, III, IV

(2) 进阶题目

lc31: Next Permutation: 经典算法，背吧
Previous Permutation
lc89: Gray Code

(3) 由 combination / permutation 延伸出来的 DFS 类型的题目

1) 一维层面

lc22: Generate Parentheses

lc17: Letter Combination of a Phone number

lc93: Restore IP Address

lc131: Palindrome Partitioning I (第一种解法)

2）二维层面

lc130: Surrounded Regions

lc79: Word search

lc51 & lc52: N-Queens I, II

lc37: Sudoku solver