# Permutation and Combination

* 基本题，但是非常重要，把这些题目做熟是必须的。
* 基本上来说，这类题的解法都是 DFS，程序的大体框架非常类似，只是根据题目的要求代码稍作修改。当然每道题也有不同的解法，但是你应该根据自己的喜好把这类题目的解决方案统一化。熟悉了这类题目以后对于 DFS 的理解会非常深刻。基本上一般的 DFS 的题目应该没什么问题了。
* 无论是排列还是组合，这类题都有一个变形，就是要求不能有重复的输出。PIE 和 CC150&#x20;

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

  时候比较容易跪的题目。

## (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
```
