491.递增子序列
文章：14. 递增子序列
题目：491. 递增子序列
【思路】
90.子集中我们是通过排序，再加一个标记数组来达到去重的目的。
而本题求自增长子序列，不能对原数组进行排列，排列完的数组不符合题意。
因此我们需要使用新的去重逻辑。
回溯三部曲
本题求子序列，因此一个元素不能重复使用，需要使用startIndex来调整下一层递归的起始位置
本题需要我们遍历整颗树形结构，终止条件那不需要return。
同一父节点下的同层上使用过的元素就不能再使用了。
去重：在树层上去重（该节点会包含3），在树枝上不去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
List<List<Integer>>res = new ArrayList<>();
LinkedList<Integer>path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums,0);
return res;
}
public void backtracking(int[] nums,int startIndex){
if(path.size() > 1){
res.add(new ArrayList<>(path));
}
Set<Integer>set = new HashSet<>();
for(int i = startIndex;i<nums.length;i++){
if(!path.isEmpty() && nums[i] <path.get(path.size()-1) || set.contains(nums[i]))continue;
path.add(nums[i]);
set.add(nums[i]);
backtracking(nums,i+1);
path.removeLast();
}
}
}
|
要整理一下go的语法！
1
2
|
if len(path) == 0 || nums[i]>=path[len(path)-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| func findSubsequences(nums []int) [][]int {
res,path := make([][]int,0),make([]int,0,len(nums))
var dfs func(nums []int,s int)
dfs = func(nums []int,s int){
if len(path) > 1{
tmp := make([]int,len(path))
copy(tmp,path)
res = append(res,tmp)
}
used :=make(map[int]bool,len(path))
for i:= s;i<len(nums);i++{
if used[nums[i]]{
continue
}
if len(path) == 0 || nums[i]>=path[len(path)-1]{
path=append(path,nums[i])
used[nums[i]] = true
dfs(nums,i+1)
path = path[:len(path)-1]
}
}
}
dfs(nums,0)
return res
}
|
46.全排列
文章：15. 全排列
题目：46. 全排列
【思路】
回溯三部曲
排列是有序的，我们需要重复利用之前使用过的数值，因此我们处理当前问题的时候不需要再使用startIndex了。
但是排列问题需要一个used数组，标记已经选择的元素。
叶子节点（path的长度等于nums的长度时）就是收割结果的地方。
used数组标记当前索引true后进入回溯，去重。
在回溯之后将used标记当前索引false，使得下一轮迭代再次使用该值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
List<List<Integer>>res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
dfs(nums,0);
return res;
}
public void dfs(int[] nums,int cur){
if(cur == nums.length){
res.add(new ArrayList<>(path));
}
for(int i =0 ;i < nums.length;i++){
if(!used[i]){
path.add(nums[i]);
used[i] = true;
dfs(nums,cur+1);
path.removeLast();
used[i] = false;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func permute(nums []int) [][]int {
res,path := make([][]int,0),make([]int,0,len(nums))
st := make([]bool,len(nums))
var dfs func(nums []int,cur int)
dfs = func(nums []int, cur int){
if len(nums) == cur{
tmp := make([]int,len(path))
copy(tmp,path)
res = append(res,tmp)
}
for i:=0 ;i < len(nums);i++{
if !st[i]{
path = append(path,nums[i])
st[i] = true
dfs(nums,cur+1)
path = path[:len(path)-1]
st[i]=false
}
}
}
dfs(nums,0)
return res
}
|
47.全排列II
文章：16. 全排列II
题目：47. 全排列 II
【思路】
本题和上一题的区别是：给定一个可能包含重复数字的序列，要返回所有不重复的全排列。
去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
我们对同一树层，前一位（nums[i-1]）如果使用过，那么就进行去重。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
Java实现
思路相似，多了去除重复出现的值。
if(i > 0 && nums[i-1] == nums[i] && used[i-1] == false)continue;
判断 同一层树的前一位和后一位是否相等、used[i-1] == false说明同一树层nums[i-1]使用过（说明重复出现），的话就跳过这一循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
List<List<Integer>>res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
dfs(nums,0);
return res;
}
public void dfs(int[] nums,int cur){
if(cur == nums.length){
res.add(new ArrayList<>(path));
}
for(int i =0 ;i < nums.length;i++){
if(i > 0 && nums[i-1] == nums[i] && used[i-1] == false)continue;
if(!used[i] ){
path.add(nums[i]);
used[i] = true;
dfs(nums,cur+1);
path.removeLast();
used[i] = false;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func permuteUnique(nums []int) [][]int {
res := make([][]int,0)
path := make([]int,0,len(nums))
st := make([]bool,len(nums))
var dfs func(nums []int,cur int)
dfs = func(nums []int ,cur int){
if len(nums) == cur{
tmp:= make([]int,len(path))
copy(tmp,path)
res = append(res,tmp)
}
for i :=0;i<len(nums) ;i++{
if i>0 && nums[i-1] == nums[i] && st[i-1] == false{
continue
}
if !st[i]{
path = append(path,nums[i])
st[i] = true
dfs(nums,cur+1)
path = path[:len(path)-1]
st[i] = false
}
}
}
dfs(nums,0)
return res
}
|
【算法总结】
递增子序列：需要使用回溯的方法，子序列需要我们遍历整个树形结构除了第一层以外的节点，由于求的是递增子序列，因此我们需要判断前一个值是否大于当前值，是的话直接忽略该枝干，不是的话则添加进入path继续进行遍历。
全排列：需要使用回溯的方法，要保证进入回溯之后当前索引的值不能够被再次添加进数组，因此 我们使用了一个bool数组对下标是否使用过进行保存，然后回溯判断添加值。
全排列II：需要使用回溯的方法，在上题的基础上还需要我们去重，即判断前一个值是否等于当前值且保证前一个值被使用过：
used[i - 1] == true，说明同一树枝nums[i - 1]使用过
used[i - 1] == false，说明同一树层nums[i - 1]使用过
如果同一树层nums[i - 1]使用过则直接跳过
【语法总结】
关于make语句：
tmp := make([]int, len(path))：这行代码创建了一个整数切片tmp，其长度与path切片的长度相同。此时，tmp切片中的元素将使用默认值进行初始化（对于int类型，默认值为0）。
使用append函数：[0,0,0,1,2,3…]
tmp := make([]int, 0, len(path))：这行代码创建了一个空的整数切片tmp，其容量为len(path)。这意味着tmp切片在添加新元素时可以使用len(path)个空间，从而避免在添加元素时频繁地进行内存分配。初始时，tmp切片不包含任何元素。
使用append函数：[1,2,3…]
