Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit c269a60

Browse filesBrowse files
committed
Add backtrack.md
1 parent 71d1631 commit c269a60
Copy full SHA for c269a60

File tree

Expand file treeCollapse file tree

2 files changed

+310
-15
lines changed
Filter options
Expand file treeCollapse file tree

2 files changed

+310
-15
lines changed

‎README.md

Copy file name to clipboard
+28-15Lines changed: 28 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,46 @@
1-
# 算法模板
1+
# 算法模板(Java版)
22

3-
> 本项目fork自[算法模板](https://github.com/greyireland/algorithm-pattern),在此感谢原作者的整理与贡献
3+
> 本项目内容主要参考[算法模板](https://github.com/greyireland/algorithm-pattern),在此感谢原作者的整理与贡献
44
5-
在原项目的基础上,做了一点微小的工作
5+
在原项目的基础上,尽量保持了原有的结构划分,并做了一点微小的工作
66

77
- 代码改写为`java`语言版本
8-
- 调整部分内容,加入了自己的思考
8+
- 调整部分内容,新增了几种算法
99
- 补充部分[leetcode中国站](https://leetcode-cn.com/)的题目链接
1010

11-
尽量保持了原有的结构划分,没有增加多余的内容。
12-
1311
## 核心内容
1412

15-
### 数据结构篇
13+
### 数据结构
1614

17-
- [二叉树](./data_structure/binary_tree.md)
1815
- [链表](./data_structure/linked_list.md)
1916
- [栈和队列](./data_structure/stack_queue.md)
20-
- [二进制](./data_structure/binary_op.md)
17+
- [二叉树](./data_structure/binary_tree.md)
2118

22-
### 基础算法篇
19+
### 基础算法
2320

21+
- [滑动窗口](./basic_algorithm/slide_window.md)
22+
- [递归算法](./basic_algorithm/recursion.md)
23+
- [回溯算法](./basic_algorithm/backtrack.md)
2424
- [二分搜索](./basic_algorithm/binary_search.md)
2525
- [排序算法](./basic_algorithm/sort.md)
2626
- [动态规划](./basic_algorithm/dp.md)
2727

28-
### 算法思维
28+
### 进阶算法
29+
30+
> 此处整理了一些不常见但是在特殊场景下很有效的算法
31+
32+
- [快速选择](./advanced_algorithm/quick_select.md)
33+
- [三向切分快速排序](./advanced_algorithm/three_way_quick_sort.md)
34+
- [二进制运算](./advanced_algorithm/binary_op.md)
35+
36+
## 刷题建议
37+
38+
1. 巩固基础:先从数据结构的基础题做起,掌握常见数据结构以及对应操作的实现
39+
2. 算法专题:推荐按类型刷题,在几天之内做完同一种类型的题目,可以迅速理解
40+
3. 查漏补缺:对于某些不常见的特殊解法,在最后快速刷掉,务必留下印象
41+
42+
> ### 欢迎 star 本项目
43+
44+
![](https://licensebuttons.net/l/by-nc-sa/4.0/88x31.png)
2945

30-
- [递归思维](./advanced_algorithm/recursion.md)
31-
- [滑动窗口思想](./advanced_algorithm/slide_window.md)
32-
- [二叉搜索树](./advanced_algorithm/binary_search_tree.md)
33-
- [回溯法](./advanced_algorithm/backtrack.md)
46+
本项目采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议</a>进行许可。

‎basic_algorithm/backtrack.md

Copy file name to clipboard
+282Lines changed: 282 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,282 @@
1+
# 回溯算法
2+
3+
## 背景
4+
5+
回溯法(backtrack)常用于遍历列表所有子集,是 DFS 深度搜索一种,一般用于全排列,穷尽所有可能,遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!),它不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。
6+
7+
## 模板
8+
9+
```go
10+
result = []
11+
func backtrack(选择列表,路径):
12+
if 满足结束条件:
13+
result.add(路径)
14+
return
15+
for 选择 in 选择列表:
16+
做选择
17+
backtrack(选择列表,路径)
18+
撤销选择
19+
```
20+
21+
核心就是从选择列表里做一个选择,然后一直递归往下搜索答案,如果遇到路径不通,就返回来撤销这次选择。
22+
23+
## 常见例题
24+
25+
### 集合类
26+
27+
#### 子集
28+
29+
> [78. 子集](https://leetcode-cn.com/problems/subsets/)
30+
>
31+
> 给你一个整数数组 `nums` ,数组中的元素 **互不相同** 。返回该数组所有可能的子集(幂集)。
32+
33+
```java
34+
public List<List<Integer>> subsets(int[] nums) {
35+
// 保存中间结果
36+
List<Integer> subSet = new ArrayList<>();
37+
// 保存最终结果
38+
List<List<Integer>> result = new ArrayList<>();
39+
backtrack(nums, 0, subSet, result);
40+
return result;
41+
}
42+
43+
// nums 给定的集合
44+
// pos 下次添加到集合中的元素位置索引
45+
// subSet 临时结果集合(每次需要复制保存)
46+
// result 最终结果
47+
private void backtrack(int[] nums, int pos, List<Integer> subSet, List<List<Integer>> result) {
48+
// 把临时结果复制出来保存到最终结果
49+
result.add(new ArrayList<>(subSet));
50+
for (int i = pos; i < nums.length; i++) {
51+
// 选择、处理结果、再撤销选择
52+
subSet.add(nums[i]);
53+
backtrack(nums, i+1, subSet, result);
54+
subSet.remove(subSet.size() - 1);
55+
}
56+
}
57+
```
58+
59+
#### 子集 II
60+
61+
> [90. 子集 II](https://leetcode-cn.com/problems/subsets-ii/)
62+
>
63+
> 给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集。
64+
65+
```java
66+
public List<List<Integer>> subsets(int[] nums) {
67+
// 保存中间结果
68+
List<Integer> subSet = new ArrayList<>();
69+
// 保存最终结果
70+
List<List<Integer>> result = new ArrayList<>();
71+
// 先排序
72+
Arrays.sort(nums);
73+
backtrack(nums, 0, subSet, result);
74+
return result;
75+
}
76+
77+
// nums 给定的集合
78+
// pos 下次添加到集合中的元素位置索引
79+
// subSet 临时结果集合(每次需要复制保存)
80+
// result 最终结果
81+
private void backtrack(int[] nums, int pos, List<Integer> subSet, List<List<Integer>> result) {
82+
// 把临时结果复制出来保存到最终结果
83+
result.add(new ArrayList<>(subSet));
84+
for (int i = pos; i < nums.length; i++) {
85+
// 排序之后,如果再遇到重复元素,则不选择此元素
86+
if (i != pos && nums[i] == nums[i-1]) {
87+
continue;
88+
}
89+
// 选择、处理结果、再撤销选择
90+
subSet.add(nums[i]);
91+
backtrack(nums, i+1, subSet, result);
92+
subSet.remove(subSet.size() - 1);
93+
}
94+
}
95+
```
96+
97+
### 排列类
98+
99+
#### 全排列
100+
101+
> [46. 全排列](https://leetcode-cn.com/problems/permutations/)
102+
>
103+
> 给定一个 **没有重复** 数字的序列,返回其所有可能的全排列。
104+
105+
思路:需要记录已经选择过的元素,满足条件的结果才进行返回。这里要注意在做选择时记录,回溯时撤销。
106+
107+
```java
108+
public List<List<Integer>> permute(int[] nums) {
109+
List<Integer> list = new ArrayList<>();
110+
List<List<Integer>> result = new ArrayList<>();
111+
// 标记这个元素是否已经添加到结果集
112+
boolean[] visited = new boolean[nums.length];
113+
backtrack(nums, visited, list, result);
114+
return result;
115+
}
116+
117+
// nums 输入集合
118+
// visited 当前递归标记过的元素
119+
// list 临时结果集(路径)
120+
// result 最终结果
121+
private void backtrack(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> result) {
122+
if (list.size() == nums.length) {
123+
result.add(new ArrayList<>(list));
124+
return;
125+
}
126+
for (int i = 0; i < nums.length; i++) {
127+
// 已经添加过的元素,直接跳过
128+
if (visited[i]) {
129+
continue;
130+
}
131+
// 添加元素
132+
list.add(nums[i]);
133+
visited[i] = true;
134+
backtrack(nums, visited, list, result);
135+
// 移除元素
136+
list.remove(list.size() - 1);
137+
visited[i] = false;
138+
}
139+
}
140+
```
141+
142+
#### 全排列 II
143+
144+
> [47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)
145+
>
146+
> 给定一个可包含重复数字的序列,返回所有不重复的全排列。
147+
148+
```java
149+
public List<List<Integer>> permuteUnique(int[] nums) {
150+
List<Integer> list = new ArrayList<>();
151+
List<List<Integer>> result = new ArrayList<>();
152+
// 标记这个元素是否已经添加到结果集
153+
boolean[] visited = new boolean[nums.length];
154+
// 先排序
155+
Arrays.sort(nums);
156+
backtrack(nums, visited, list, result);
157+
return result;
158+
}
159+
160+
// nums 输入集合
161+
// visited 当前递归标记过的元素
162+
// list 临时结果集
163+
// result 最终结果
164+
private void backtrack(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> result) {
165+
if (list.size() == nums.length) {
166+
result.add(new ArrayList<>(list));
167+
return;
168+
}
169+
for (int i = 0; i < nums.length; i++) {
170+
// 已经添加过的元素,直接跳过
171+
if (visited[i]) {
172+
continue;
173+
}
174+
// 上一个元素和当前相同,并且没有访问过就跳过
175+
if (i != 0 && nums[i] == nums[i-1] && !visited[i-1]) {
176+
continue;
177+
}
178+
list.add(nums[i]);
179+
visited[i] = true;
180+
backtrack(nums, visited, list, result);
181+
list.remove(list.size() - 1);
182+
visited[i] = false;
183+
}
184+
}
185+
186+
```
187+
188+
### 组合类
189+
190+
#### 组合总和
191+
192+
> [39. 组合总和](https://leetcode-cn.com/problems/combination-sum/)
193+
>
194+
> 给定一个**无重复元素**的数组 `candidates` 和一个目标数 `target` ,找出 `candidates` 中所有可以使数字和为 `target` 的组合。
195+
>
196+
> `candidates` 中的数字可以无限制重复被选取。
197+
>
198+
> **说明:**
199+
>
200+
> - 所有数字(包括 `target`)都是正整数。
201+
> - 解集不能包含重复的组合。
202+
203+
```java
204+
public List<List<Integer>> combinationSum(int[] candidates, int target) {
205+
List<Integer> answer = new ArrayList();
206+
List<List<Integer>> result = new ArrayList();
207+
// 先排序
208+
Arrays.sort(candidates);
209+
backtrack(candidates, 0, target, answer, result);
210+
return result;
211+
}
212+
213+
// candidates 输入集合
214+
// pos 当前标记位置,标记前的元素不再考虑
215+
// target 求和目标
216+
// answer 临时解法
217+
// result 最终结果
218+
private void backtrack(int[] candidates, int pos, int target, List<Integer> answer, List<List<Integer>> result) {
219+
if (target == 0) {
220+
result.add(new ArrayList<>(answer));
221+
}
222+
for (int i = pos; i < candidates.length; i++) {
223+
// 剪枝:后续元素都比目标大,直接break(比continue要快)
224+
if (candidates[i] > target) {
225+
break;
226+
}
227+
// 添加元素
228+
answer.add(candidates[i]);
229+
// 元素可以重复取,所以从当前位置继续
230+
backtrack(candidates, i, target - candidates[i], answer, result);
231+
// 移除元素
232+
answer.remove(answer.size() - 1);
233+
}
234+
}
235+
```
236+
237+
#### 电话号码的字母组合
238+
239+
> [17. 电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
240+
>
241+
> 给定一个仅包含数字 `2-9` 的字符串,返回所有它能表示的字母组合。答案可以按 **任意顺序** 返回。
242+
>
243+
> 数字到字母的映射与电话按键相同
244+
245+
```java
246+
// 记录数字到字母的映射
247+
private final static Map<Character, String> map = new HashMap<>();
248+
249+
static {
250+
map.put('2', "abc");
251+
map.put('3', "def");
252+
map.put('4', "ghi");
253+
map.put('5', "jkl");
254+
map.put('6', "mno");
255+
map.put('7', "pqrs");
256+
map.put('8', "tuv");
257+
map.put('9', "wxyz");
258+
}
259+
260+
public List<String> letterCombinations(String digits) {
261+
StringBuilder builder = new StringBuilder();
262+
List<String> result = new ArrayList<>();
263+
backtrack(digits, 0, builder, result);
264+
return result;
265+
}
266+
267+
private void backtrack(String digits, int pos, StringBuilder builder, List<String> result) {
268+
// 结束条件:到达末尾
269+
if (pos == digits.length()) {
270+
// 如果原字符串为空则没有对应的字母组合
271+
if (pos != 0) {
272+
result.add(builder.toString());
273+
}
274+
return;
275+
}
276+
for (char c : map.get(digits.charAt(pos)).toCharArray()) {
277+
builder.append(c);
278+
backtrack(digits, pos + 1, builder, result);
279+
builder.deleteCharAt(builder.length() - 1);
280+
}
281+
}
282+
```

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.