《代码随想录》回溯算法：递增子序列
本题的完整题目如下：
本题的完整思路如下： 1.本题使用递归和回溯来求解，所以分为三部： 2.第一步：确定递归函数的返回值和参数：返回值无，参数为原数组和遍历开始索引startindex。 3.第二步：确定递归函数终止条件：本题与前边的题不一样，收割结果的条件与递归终止的条件不是同时发生了，所以要先收割结果，再返回。返回条件依然是startindex>=原数组长度。其实这道题不需要终止条件也可以，因为for循环结束时，该递归函数也就结束了。 3.第三步：确定单次递归函数中的逻辑：由于原数组中存在相同元素，所以需要去重，但是本题由于结果与原数组中的顺序有关，所以不能对原数组进行排序然后去重，所以本题去重是难点！在每一层遍历时，创建一个新的哈希集合used，每次遍历一个元素时，就将该元素添加到used集合中。在每次遍历时，判断当前元素在used集合中是否存在，如果存在，就不进行下边的递归与回溯。除此之外，还需要判断当前元素是否满足题里的要求：递增序列，即判断当前元素是否大于等于前一个元素，如果不满足，就continue。如果以上条件都满足，就进行递归和回溯。** 4.本题去重步骤是关键，一种全新的去重方法。 以下是本题的完整代码：
//491.非递减子序列
class Solution10 {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {
backtrack(nums, 0);return res;}
public void backtrack(int[] nums, int startindex) {if(path.size() >= 2) {res.add(new ArrayList<>(path));}
if(startindex >= nums.length) {return;}
HashSet<Integer> used = new HashSet<>();
for(int i = startindex; i < nums.length; i++) {if(!path.isEmpty() && nums[i] < path.get(path.size() - 1) || used.contains(nums[i])) {continue;}path.add(nums[i]);used.add(nums[i]);backtrack(nums, i + 1);path.remove(path.size() - 1);}}
}
《代码随想录》回溯算法：全排列
本题的完整题目如下：
本题的完整思路如下： 1.本题与前边的题不一样，前边的题是组合，而该题是排列。组合问题中，引入了一个变量startindex来控制下次遍历时从当前元素的下一个元素开始遍历，而排列问题不是，排列问题需要遍历数组中的所有元素，所以需要引入一个数组来表明哪些元素还没有遍历，直到所有元素都遍历，才结束。 2.所以本题分为三部： 3.第一步：确定递归函数的返回值和参数：返回值无，参数是原数组和used数组，该数组为boolean数组，大小与原数组一致。 4.第二步：确定递归函数的终止条件：由于是排列问题，所以当path集合的大小与原数组大小一样时，表明所有元素都遍历过一遍了，此时可以结束。，存储结果，返回。 5.第三步：确定单次递归函数中的逻辑：for循环的起始值不是从startindex开始了，此时需要从0开始，一直到数组的所有元素都被遍历。所以在遍历时，首先判断当前索引对应的used数组中的值是否为false，如果为true则表明当前元素已经被遍历过了，continue。如果为false，则进行遍历，回溯。 6.本题的关键在于区分清楚排序与组合问题的不同之处，怎么区分该元素是否已经被遍历过，怎么将原数组中的所有元素都遍历一遍。 本题的完整代码如下：
//46.全排列
class Solution11 {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];backtrack(nums, used);return res;}public 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++) {if(used[i] == true) {continue;}path.add(nums[i]);used[i] = true;backtrack(nums, used);path.remove(path.size() - 1);used[i] = false;}}
}
《代码随想录》回溯算法：全排列II
本题的完整题目如下：
本题的完整思路如下： 1.本题与上一题的区别是该题中的数组元素中存在重复值，所以涉及到去重问题，但是由于将原数组排序后得出的结果与排序前的结果是一样的，因为是排序问题。所以该题相比上题就多一个排序的过程，再判断是否重复即可。 完整代码如下：
//46.全排列Ⅱ
class Solution12 {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.sort(nums);backtrack(nums, used);return res;}public 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++) {if(i >=1 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if(used[i] == true) {continue;}path.add(nums[i]);used[i] = true;backtrack(nums, used);path.remove(path.size() - 1);used[i] = false;
}}
}
