今日内容
- Leetcode. 491 递增子序列
- Leetcode. 46 全排列
- Leetcode. 47 全排列Ⅱ
Leetcode. 491 递增子序列
文章链接：代码随想录 (programmercarl.com)
题目链接：491. 非递减子序列 - 力扣（LeetCode）
本题也是一个子集问题，根据题意也知道要去重，提到去重就会不自觉地想到 90. 子集 II - 力扣（LeetCode）中的去重。但在本题中不能使用 Leetcode. 90 这种去重思想，因为这种去重需要对数组进行排序，而本题如果进行排序，会对得到的结果产生影响。
所以本题的去重应该用一个 Set 来记录本层已经使用过的元素。
根据上述内容，可写出代码：
class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex){if (elem.size() >= 2){result.add(new LinkedList<>(elem));}if (startIndex == nums.length){return;}Set<Integer> used = new HashSet<>(); // 记录已使用元素的Setfor (int i = startIndex; i < nums.length; i++){if (!elem.isEmpty() && nums[i] < elem.get(elem.size() - 1) || used.contains(nums[i])){continue;}used.add(nums[i]);elem.add(nums[i]);backtracking(nums, i + 1);elem.remove(elem.size() - 1);}}
}- 时间复杂度：O(n * 2 ^ n)
- 空间复杂度：O(n)
Leetcode. 46 全排列
文章链接：代码随想录 (programmercarl.com)
题目链接：46. 全排列 - 力扣（LeetCode）
本题是回溯问题中的排列问题， 排列问题和组合问题不同，排列问题返回得结果是有序的，比如{1, 2} {2, 1} 在排列问题中是两个不同的结果。
也正因为结果有序，所以和组合问题、分割问题以及子集问题不同，排列问题每次搜索都要从头开始，所以不需要startIndex指示下一次搜索开始的位置。
虽然排列问题不需要startIndex了，但是它返回的结果是有序的，元素的排列顺序依然需要其他变量进行标识。因此需要使用一个数组来记录每个元素的使用情况。
本题中，我们使用一个布尔数组 used 来标识每个元素的使用情况，当本层遍历使用到该元素后，该元素在used数组中的值被赋为 true。在遍历元素时，就可以根据 used 数组中对应索引的值来判断是否被使用，被使用就跳过。
排列问题经过抽象得到的树形结构图如下所示：
根据上述内容，写出如下代码：
class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length]; // 记录元素的使用情况backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used){if (elem.size() == nums.length){result.add(new LinkedList<>(elem));return;}for (int i = 0; i < nums.length; i++){if (used[i]){continue;} // 若元素已使用过，则跳过该元素elem.add(nums[i]);used[i] = true; // 元素被使用，赋值为truebacktracking(nums, used);used[i] = false; // 回溯elem.remove(elem.size() - 1); }}
}- 时间复杂度：O(n!)
- 空间复杂度：O(n)
Leetcode. 47 全排列Ⅱ
文章链接：代码随想录 (programmercarl.com)
题目链接：47. 全排列 II - 力扣（LeetCode）
本题可以看作是 Leetcode. 46 + Leetcode. 90 的结合，也就是在全排列问题中加入去重。
代码如下：
class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.sort(nums); // 注意一定要排序backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used){if (elem.size() == nums.length){result.add(new LinkedList<>(elem));return;}for (int i = 0; i < nums.length; i++){if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true){ // 判断元素是否被使用以及去重continue;}if (used[i]){continue;}elem.add(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;elem.remove(elem.size() - 1);}}
}- 时间复杂度：O(n! * n)
- 空间复杂度：O(n)
总结
第一题是去重的不同，去重时注意所给数据是否有序，有序的话就可以使用 Leetcode. 90 的去重思想；无序的话就需要其他容器记录已使用元素。
排列问题要求结果有序，所以每次遍历都需要从头开始，并且需要一个容器记录哪些元素被使用过，注意这里的标识不是为了去重，而是为了调整结果顺序。
去重和判断元素使用情况的区别，从Leetcode. 47 就可以看出来了。
