刷题小记：
排列问题和组合问题都在叶子节点收获，切割问题和序列问题都在符合条件的任意节点收获。
切割问题无需设置startIndex。
491.非递减子序列（491.非递减子序列）
题目分析：
给定一个整数数组nums，找出并返回该数组中不同的递增子序列，要求递增子序列中至少有两个元素。
注意：数组中可能包含重复元素，若两个整数相等，也视作递增序列的一种特殊情况。
解题思路：
子序列与子集的定义不同：
- 子集与元素间的次序无关
- 子序列与元素间的次序有关
因此，对于数组中包含重复元素的情况，不能使用先排序，再去重的方式进行去重。
考虑在每个树层使用一个Set，记录该树层遍历过的元素值，以避免在同一树层遍历重复元素。
解题步骤：
- 回溯的参数：整数数组nums，遍历起点startIndex
- 无返回值
- 回溯的终止条件：若子序列长度至少为2，则将其添加至返回列表
- 回溯的搜索遍历逻辑：
-
- i从startIndex开始遍历
-
-
- 如果nums[i]在set中存在，那么跳过本轮
- 如果该元素不能使子序列非递减，那么跳过本轮
- 添加nums[i]至当前树层的set
- 添加nums[i]至子序列
- 将i+1作为new_startIndex传入递归
- 将子序列末尾元素弹出
-
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> increasingArray = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return resList;}public void backtracking(int[] nums, int startIndex) {if (increasingArray.size() >= 2) {resList.add(new ArrayList<>(increasingArray));}Set<Integer> set = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {if ((increasingArray.size() > 0 && increasingArray.get(increasingArray.size()-1) > nums[i]) || set.contains(nums[i])) continue;set.add(nums[i]);increasingArray.add(nums[i]);backtracking(nums, i+1);increasingArray.remove(increasingArray.size()-1);}}
}46.全排列（46.全排列）
题目分析：
给定一个不含重复数字的数组nums，返回其所有可能的全排列，按任意顺序返回答案。
解题思路：
考虑用一个used数组标注已使用的元素（1代表使用，0代表未用），从而在避免元素重复使用的同时，实现对未用元素的遍历取用。
解题步骤：
初始化一个和nums数组等长的used数组，回溯遍历如下：
- 回溯的参数：nums，used
- 无返回值
- 回溯的终止条件：path的长度等于nums的长度，则将其返回
- 回溯的搜索遍历逻辑：
-
- 用指针i遍历used数组：
-
-
- 若used[i]为0
-
-
-
-
- 将nums[i]加入path
- 标注used[i]为1
- 将nums和used传入回溯函数进行递归
- 重置used[i]为0
- 将path末尾的元素删去
-
-
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {backtracking(nums,new int[nums.length]);return resList;}public void backtracking(int[] nums, int[] used) {if (path.size() == nums.length) {resList.add(new ArrayList<>(path));return;}for (int i = 0; i < used.length; i++) {if (used[i] != 0) continue;path.add(nums[i]);used[i] = 1;backtracking(nums, used);used[i] = 0;path.remove(path.size()-1);}}
}47.全排列Ⅱ（47.全排列Ⅱ）
题目分析：
给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。
解题思路：
由于可能包含重复数字，故参考40.组合总和Ⅱ，通过先排序，再剪枝的方式进行去重。其余部分，基于46.全排列实现即可。
解题步骤：
先将nums数组进行排序。
初始化一个和nums数组等长的used数组，回溯遍历如下：
- 回溯的参数：nums，used
- 无返回值
- 回溯的终止条件：path的长度等于nums的长度，则将其返回
- 回溯的搜索遍历逻辑：
-
- 用指针i遍历used数组：
-
-
- 若i>0时，nums[i] == nums[i-1]且used[i-1] != 0，即该元素在该树层已使用过，那么跳过该轮循环
- 若used[i] == 1，那么也跳过该轮循环
- 将nums[i]加入path
- 标注used[i]为1
- 将nums和used传入回溯函数进行递归
- 重置used[i]为0
- 将path末尾的元素删去
-
补充：
if (i > 0 && used[i-1] != 0 && nums[i] == nums[i-1]) continue;
这一行，将used[i-1] != 1也可以，这种方法是树枝去重，参考代码随想录：0047全排列Ⅱ，示意如下：
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);backtracking(nums, new int[nums.length]);return resList;}public void backtracking(int[] nums, int[] used) {if (path.size() == nums.length) {resList.add(new ArrayList<>(path));return;}for (int i = 0; i < used.length; i++) {if (i > 0 && used[i-1] != 0 && nums[i] == nums[i-1]) continue;// 树层去重if (used[i] != 0) continue;// 避免重复使用同一元素path.add(nums[i]);used[i] = 1;backtracking(nums, used);used[i] = 0;path.remove(path.size()-1);}}
}
