0%

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
• 282 Expression Add Operators
• 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 (_a_1, _a_2, … , _a_k) must be in non-descending order. (ie, _a_1 ≤ _a_2 ≤ … ≤ _a_k).
• 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 (_a_1, _a_2, … , _a_k) must be in non-descending order. (ie, _a_1 ≤ _a_2 ≤ … ≤ _a_k).
• 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

Follow up for N-Queens problem.

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

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]

### 282. Expression Add Operators

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