* 491.递增子序列
* 46.全排列
* 47.全排列 II
详细布置
491.递增子序列
https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV1EG4y1h78回溯三部曲
- 递归函数参数
本题求子序列，很明显一个元素不能重复使用，所以需要startIndex，调整下一层递归的起始位置。
- 终止条件
本题其实类似求子集问题，也是要遍历树形结构找每一个节点，所以和回溯算法：求子集问题！(opens new window)一样，可以不加终止条件，startIndex每次都会加1，并不会无限递归。
- 单层搜索逻辑
同一父节点下的同层上使用过的元素就不能再使用了
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums,0);
return res;
}
private void backtracking(int[] nums, int start) {
if (path.size() > 1) {
res.add(new ArrayList<>(path));
}
int[] used = new int[201];// 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
for (int i = start; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
(used[nums[i] + 100] == 1)) {
continue;
}
used[nums[i] + 100] = 1;// 记录这个元素在本层用过了，本层后面不能再用了
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
info
解答成功:
执行耗时:5 ms,击败了61.98% 的Java用户
内存消耗:47.2 MB,击败了66.78% 的Java用户
//法二：使用map
class Solution {
//结果集合
List<List<Integer>> res = new ArrayList<>();
//路径集合
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
getSubsequences(nums,0);
return res;
}
private void getSubsequences( int[] nums, int start ) {
if(path.size()>1 ){
res.add( new ArrayList<>(path) );
// 注意这里不要加return，要取树上的节点
}
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=start ;i < nums.length ;i++){
if(!path.isEmpty() && nums[i]< path.getLast()){
continue;
}
// 使用过了当前数字
if ( map.getOrDefault( nums[i],0 ) >=1 ){
continue;
}
map.put(nums[i],map.getOrDefault( nums[i],0 )+1);
path.add( nums[i] );
getSubsequences( nums,i+1 );
path.removeLast();
}
}
}
46.全排列
本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex
https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W
思路：回溯三部曲
- 递归函数参数
首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
- 递归终止条件
可以看出叶子节点，就是收割结果的地方。
那么什么时候，算是到达叶子节点呢？
当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
- 单层搜索的逻辑
这里和77.组合问题(opens new window)、131.切割问题(opens new window)和78.子集问题(opens new window)最大的不同就是for循环里不用startIndex了。
因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。
而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) {
return result;
}
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(int[] nums) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
//info
解答成功:
执行耗时:1 ms,击败了82.38% 的Java用户
内存消耗:41.8 MB,击败了43.08% 的Java用户
47.全排列 II
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行
https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm
思路：
对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
在46.全排列(opens new window)中已经详细讲解了排列问题的写法，在40.组合总和II(opens new window)、90.子集II(opens new window)中详细讲解了去重的写法，代码如下：
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
backTrack(nums, used);
return res;
}
private void backTrack(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.add(nums[i]);
backTrack(nums, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
}
//info
解答成功:
执行耗时:1 ms,击败了99.82% 的Java用户
内存消耗:42.3 MB,击败了37.27% 的Java用户
标签：排列,nums,46,随想录,int,used,new,path
From： https://www.cnblogs.com/gaoyuan2lty/p/17048339.html