Skip to content

Commit c63d288

Browse files
da183da183
committed
back track permutation questions
1 parent 41dc1b3 commit c63d288

File tree

1 file changed

+115
-130
lines changed

1 file changed

+115
-130
lines changed

‎advanced_algorithm/backtrack.md‎

Lines changed: 115 additions & 130 deletions
Original file line numberDiff line numberDiff line change
@@ -6,11 +6,11 @@
66

77
## 模板
88

9-
```go
10-
result = []
11-
func backtrack(选择列表,路径):
9+
```c++
10+
vector<T> result;
11+
void backtrack(选择列表,路径):
1212
if 满足结束条件:
13-
result.add(路径)
13+
result.push_back(路径);
1414
return
1515
for 选择 in 选择列表:
1616
做选择
@@ -30,73 +30,53 @@ func backtrack(选择列表,路径):
3030
3131
![image.png](https://img.fuiboom.com/img/backtrack.png)
3232
33-
```go
34-
func subsets(nums []int) [][]int {
35-
// 保存最终结果
36-
result := make([][]int, 0)
37-
// 保存中间结果
38-
list := make([]int, 0)
39-
backtrack(nums, 0, list, &result)
40-
return result
33+
```c++
34+
vector<vector<int>> subsets(vector<int>& nums) {
35+
vector<vector<int>> result;
36+
vector<int> track;
37+
backtrack(nums, 0, track, result);
38+
return result;
4139
}
4240
43-
// nums 给定的集合
44-
// pos 下次添加到集合中的元素位置索引
45-
// list 临时结果集合(每次需要复制保存)
46-
// result 最终结果
47-
func backtrack(nums []int, pos int, list []int, result *[][]int) {
48-
// 把临时结果复制出来保存到最终结果
49-
ans := make([]int, len(list))
50-
copy(ans, list)
51-
*result = append(*result, ans)
52-
// 选择、处理结果、再撤销选择
53-
for i := pos; i < len(nums); i++ {
54-
list = append(list, nums[i])
55-
backtrack(nums, i+1, list, result)
56-
list = list[0 : len(list)-1]
57-
}
41+
void backtrack(const vector<int> &nums, int pos, vector<int> &track, vector<vector<int>> &result) {
42+
// 插入当前组合
43+
result.push_back(track);
44+
for (int i = pos; i < nums.size(); ++i) {
45+
// 每个值，都有两种可能，包含和不包含
46+
// 先压入
47+
track.push_back(nums[i]);
48+
// 递归处理包含当前值的情况
49+
backtrack(nums, i + 1, track, result);
50+
// 弹出，向后遍历，处理不包含的情况
51+
track.pop_back();
52+
}
5853
}
5954
```
6055

6156
### [subsets-ii](https://leetcode-cn.com/problems/subsets-ii/)
6257

6358
> 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
6459
65-
```go
66-
import (
67-
"sort"
68-
)
69-
70-
func subsetsWithDup(nums []int) [][]int {
71-
// 保存最终结果
72-
result := make([][]int, 0)
73-
// 保存中间结果
74-
list := make([]int, 0)
75-
// 先排序
76-
sort.Ints(nums)
77-
backtrack(nums, 0, list, &result)
78-
return result
60+
```c++
61+
// 对数据进行排序来判断重复元素
62+
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
63+
vector<vector<int>> result;
64+
vector<int> track;
65+
sort(nums.begin(), nums.end());
66+
backtrack(nums, 0, track, result);
67+
return result;
7968
}
8069

81-
// nums 给定的集合
82-
// pos 下次添加到集合中的元素位置索引
83-
// list 临时结果集合(每次需要复制保存)
84-
// result 最终结果
85-
func backtrack(nums []int, pos int, list []int, result *[][]int) {
86-
// 把临时结果复制出来保存到最终结果
87-
ans := make([]int, len(list))
88-
copy(ans, list)
89-
*result = append(*result, ans)
90-
// 选择时需要剪枝、处理、撤销选择
91-
for i := pos; i < len(nums); i++ {
92-
// 排序之后，如果再遇到重复元素，则不选择此元素
93-
if i != pos && nums[i] == nums[i-1] {
94-
continue
95-
}
96-
list = append(list, nums[i])
97-
backtrack(nums, i+1, list, result)
98-
list = list[0 : len(list)-1]
99-
}
70+
void backtrack(const vector<int> &nums, int pos, vector<int> &track, vector<vector<int>> &result) {
71+
result.push_back(track);
72+
for (int i = pos; i < nums.size(); ++i) {
73+
if (i != pos && nums[i] == nums[i - 1]) {
74+
continue;
75+
}
76+
track.push_back(nums[i]);
77+
backtrack(nums, i + 1, track, result);
78+
track.pop_back();
79+
}
10080
}
10181
```
10282
@@ -106,40 +86,51 @@ func backtrack(nums []int, pos int, list []int, result *[][]int) {
10686
10787
思路：需要记录已经选择过的元素，满足条件的结果才进行返回
10888
109-
```go
110-
func permute(nums []int) [][]int {
111-
result := make([][]int, 0)
112-
list := make([]int, 0)
113-
// 标记这个元素是否已经添加到结果集
114-
visited := make([]bool, len(nums))
115-
backtrack(nums, visited, list, &result)
116-
return result
89+
```c++
90+
/*
91+
* 这个问题可以看作有 n 个排列成一行的空格，从左往右依此填入题目给定的 n 个数，每个数只能使用一次
92+
*
93+
* 回溯法
94+
* 不同于上面的子集问题，撤销选择时弹出了事，这里撤销后还要留待后续组合使用
95+
* 并且需要检查数字是否已经填入过
96+
*
97+
* 思路：
98+
* backtrack(fillingPos, result)，fillingPos为当前填入的位置
99+
* 若fillingPos == n，则已经完成排列
100+
* 否则，填入"未填入过"的数字，递归处理下一个位置，最后撤销当前选择，尝试以其他"未填入过"的数字来填入fillingPos
101+
*
102+
* 优化：
103+
* 不使用额外的数组来维护已经填入过的数字，降低空间复杂度
104+
* 对于nums、当前位置fillingPos
105+
* [0, fillingPos - 1]——已填入过的数字
106+
* [fillingPos, n - 1]——未填入过的数字
107+
* 每次选择时把nums[i]与nums[fillingPos]进行交换
108+
* 撤销选择时把nums[i]与nums[fillingPos]再交换一次即可
109+
*
110+
* 既然 [fillingPos, n - 1] 为未填入的数字
111+
* 偷个鸡，撤销选择时不交换，直接 ++i 可否？
112+
* 并不能
113+
* 因为原本的 nums[i] 填入 fillingPos 这一可能性已经处理过了
114+
* 如果不交换回来，for循环遍历的时候会再用到同一个数字！
115+
*/
116+
vector<vector<int>> permute(vector<int> &nums) {
117+
vector<vector<int>> result;
118+
backtrack(result, nums, 0, nums.size());
119+
return result;
117120
}
118121
119-
// nums 输入集合
120-
// visited 当前递归标记过的元素
121-
// list 临时结果集(路径)
122-
// result 最终结果
123-
func backtrack(nums []int, visited []bool, list []int, result *[][]int) {
124-
// 返回条件：临时结果和输入集合长度一致 才是全排列
125-
if len(list) == len(nums) {
126-
ans := make([]int, len(list))
127-
copy(ans, list)
128-
*result = append(*result, ans)
129-
return
122+
void backtrack(vector<vector<int>> &result, vector<int> &nums, int fillingPos, int len) {
123+
if (fillingPos == len) {
124+
// n个数字都已排列完，保存并退出
125+
result.emplace_back(nums);
126+
return;
130127
}
131-
for i := 0; i < len(nums); i++ {
132-
// 已经添加过的元素，直接跳过
133-
if visited[i] {
134-
continue
135-
}
136-
// 添加元素
137-
list = append(list, nums[i])
138-
visited[i] = true
139-
backtrack(nums, visited, list, result)
140-
// 移除元素
141-
visited[i] = false
142-
list = list[0 : len(list)-1]
128+
for (int i = fillingPos; i < len; ++i) {
129+
// 把nums[i]填入到当前位置
130+
swap(nums[i], nums[fillingPos]);
131+
backtrack(result, nums, fillingPos + 1, len);
132+
// 把顺序恢复回去
133+
swap(nums[i], nums[fillingPos]);
143134
}
144135
}
145136
```
@@ -148,47 +139,41 @@ func backtrack(nums []int, visited []bool, list []int, result *[][]int) {
148139

149140
> 给定一个可包含重复数字的序列，返回所有不重复的全排列。
150141
151-
```go
152-
import (
153-
"sort"
154-
)
155-
156-
func permuteUnique(nums []int) [][]int {
157-
result := make([][]int, 0)
158-
list := make([]int, 0)
159-
// 标记这个元素是否已经添加到结果集
160-
visited := make([]bool, len(nums))
161-
sort.Ints(nums)
162-
backtrack(nums, visited, list, &result)
163-
return result
142+
```c++
143+
vector<vector<int>> permuteUnique(vector<int> &nums) {
144+
vector<vector<int>> result;
145+
vector<int> current;
146+
vector<bool> visited(nums.size());
147+
sort(nums.begin(), nums.end());
148+
backtrack(nums, nums.size(), visited, current, result);
149+
return result;
164150
}
165151

166-
// nums 输入集合
167-
// visited 当前递归标记过的元素
168-
// list 临时结果集
169-
// result 最终结果
170-
func backtrack(nums []int, visited []bool, list []int, result *[][]int) {
171-
// 临时结果和输入集合长度一致 才是全排列
172-
if len(list) == len(nums) {
173-
subResult := make([]int, len(list))
174-
copy(subResult, list)
175-
*result = append(*result, subResult)
176-
}
177-
for i := 0; i < len(nums); i++ {
178-
// 已经添加过的元素，直接跳过
179-
if visited[i] {
180-
continue
181-
}
182-
// 上一个元素和当前相同，并且没有访问过就跳过
183-
if i != 0 && nums[i] == nums[i-1] && !visited[i-1] {
184-
continue
185-
}
186-
list = append(list, nums[i])
187-
visited[i] = true
188-
backtrack(nums, visited, list, result)
189-
visited[i] = false
190-
list = list[0 : len(list)-1]
191-
}
152+
void backtrack(vector<int> &nums, int len, vector<bool> &visited,
153+
vector<int> &current, vector<vector<int>> &result) {
154+
if (current.size() == nums.size()) {
155+
result.emplace_back(current);
156+
return;
157+
}
158+
for (int i = 0; i < nums.size(); ++i) {
159+
// 已经在组合中
160+
if (visited[i]) {
161+
continue;
162+
}
163+
// 与上一个元素相同，并且没有访问过就跳过
164+
// 没访问过？
165+
// 重复元素，只有第一个元素考虑排列组合，后面的不再考虑以免重复
166+
// 一旦第一个重复的元素被pop并设置visited为false，则其所有排列组合都已考虑完毕
167+
// 跳过后续的重复元素
168+
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
169+
continue;
170+
}
171+
current.emplace_back(nums[i]);
172+
visited[i] = true;
173+
backtrack(nums, len, visited, current, result);
174+
visited[i] = false;
175+
current.pop_back();
176+
}
192177
}
193178
```
194179

0 commit comments

Comments
 (0)