# 『leetcode』递归/DFS

leetcode dfs 归纳整理 包括：

• 17. Letter Combinations of a Phone Number
• 22. Generate Parentheses
• 39 Combination Sum
• 40 Combination Sum II
• 51 N-Queens
• 52 N-Queens II
• 77 Combinations
• 78 Subsets
• 79 Word Search
• 90 Subsets II
• 200 Number of Islands
• 216 Combination Sum III
• 241 Different Ways to Add Parentheses
• 797. All Paths From Source to Target

### 17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

C++

Python

方法二:

BFS的思想。 解相当于一颗多叉树上的遍历。 digits[i – 1] 遍历完答案为ans，则下一次就是枚举ans和当前数字digits[i] 能打出的字母的组合起来。

### 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

C++

Python

### 39. Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set `2,3,6,7` and target `7`,
A solution set is:
`[7]`
`[2, 2, 3]`

C++

Java

Python

### 40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set `10,1,2,7,6,1,5` and target `8`,
A solution set is:
`[1, 7]`
`[1, 2, 5]`
`[2, 6]`
`[1, 1, 6]`

C++

Java

Python

### 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

C++

python

### 52. N-Queens II

Now, instead outputting board configurations, return the total number of distinct solutions.

C++

python

### 77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

C++

Java

Python

### 78. Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = `[1,2,3]`, a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

C++

Java

Python

### 79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

word = `"ABCCED"`, -> returns `true`,
word = `"SEE"`, -> returns `true`,
word = `"ABCB"`, -> returns `false`.

PS:进阶篇：Word Search II

C++

Python

C++

Python

### 90. Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = `[1,2,2]`, a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

C++

Java

Python

### 200. Number of Islands

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Example 2:

### 216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

C++

### 241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are `+`, `-` and `*`.
Example 1

Input: `"2-1-1"`.

Output: `[0, 2]`
Example 2

Input: `"2*3-4*5"`

Output: `[-34, -14, -10, -10, 10]`

Given a string that contains only digits `0-9` and a target value, return all possibilities to add binary operators (not unary) `+`, `-`, or `*` between the digits so they evaluate to the target value.

Examples:

• 由于运算符的优先级，因此，分为两半，一个是pre为计算的值，一个为val为pre右方还未计算的值，对于当前的数x，进行如下的操作可以保证优先级
• 加法：pre = pre + val   val = x
• 减法： pre =  pre – val   val = -x
• 乘法：pre = pre      val = val *x
• 当前的第一个数为’0’的情况   计算完后Break

### 797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, …, graph.length – 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0—>1
| |
v v
2—>3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

Python

### 9 thoughts on “『leetcode』递归/DFS”

1. Nathan says:

非常感謝你的網站內容及詳解 帶給我在刷題的過程中很多的幫助

2. qslvhw says:

77 题都是exceed time limit，求助

• 下周考完试在解决。。。ε=ε=ε=┏(゜ロ゜;)┛

3. chengcensha says:

麻烦请教一个问题哈。为什么在subset这道题里，要ans.append(res[:])而不是ans.append(res)呢？我记得看到你解释过但是忘记在哪道题里了。。。。谢谢。

• 不用res[:]的话，添加进去的只是个类似指针的东西。 然后如果res被修改，在ans里面的也会被修改。

• chengcensha says:

多谢~~~~

4. Allianzcortex says:

combination sum2 这里代码第二处高亮看不懂啊^-^大概思路是一样的，不过我多加了一处判定条件： bool check(vector& res,vector >&ans) { for(int i=0;i

• Allianzcortex says:

已经想明白了：上面的代码思想是不让重复的出现，我的思路是让重复的出现但不允许加入容器中。sigh^……,thanks