前言
代码随想录算法训练营day29
一、Leetcode 491.递增子序列
1.题目
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1] 输出：[[4,4]]
提示：
1. 1 <= nums.length <= 15 2. -100 <= nums[i] <= 100
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/non-decreasing-subsequences
2.解题思路
方法一：二进制枚举 + 哈希
思路与算法
我们可以采取最朴素的思路，即枚举出所有的子序列，然后判断当前的子序列是否是非严格递增的。那么我们可以用什么办法来枚举所有的子序列呢？我们需要从原序列中选出一些数，来形成新的序列，即原序列的子序列。对于原序列的每一个数来说，都有两种可能的状态，即被选中或者不被选中。如果我们用 11 代表被选中，00 代表不被选中，假设一个序列长度为 33，那么选出的子序列就对应着下面的八种状态：
1. [0,0,0][0,0,0] 2. [0,0,1][0,0,1] 3. [0,1,0][0,1,0] 4. [0,1,1][0,1,1] 5. [1,0,0][1,0,0] 6. [1,0,1][1,0,1] 7. [1,1,0][1,1,0] 8. [1,1,1][1,1,1]
由此可见长度为 nn 的序列选择子序列一共会有 2n2n 种情况，这 2n2n 中情况就是区间 [0，2n−1][0，2n−1] 的所有整数的二进制表示。我们可以枚举区间 [0，2n−1][0，2n−1] 中的每一个数，然后对它做二进制数位拆分，我们会得到一个 0/10/1 序列，接着可以构造出这个 0/10/1 序列对应的子序列，然后再检查这个序列是否是非严格递增的。
当然，我们还需要解决子序列去重的问题。对于序列去重，我们可以使用串哈希算法(即 Rabin-Karp 编码，这里不了解的同学可以参考「官方题解 - 1392. 最长快乐前缀」)，即对于一个序列 a0,a1,⋯ ,an−1a0,a1,⋯,an−1，我们可以认为是一个 max{ai}+1max{ai}+1 进制的数，这个数的数值等于(记 b=max{ai}+1b=max{ai}+1)：
f(a⃗)=∑i=0n−1bi×aif(a
)=i=0∑n−1bi×ai
每次我们找到一个合法序列的时候，都去计算这个序列的哈希值，用一个哈希表来记录已有的哈希值，如果该值已经出现在哈希表中，就舍弃这个序列，否则就把这个序列加入到答案中。
在实现的过程中，我们发现这个哈希值可能非常大，我们可以将它模一个大素数 PP，将这个值映射到 intint 的范围内。所以实际上这里的哈希函数是：
f(a⃗)=∑i=0n−1bi×ai(modP)f(a
)=i=0∑n−1bi×ai(modP)
而这里的 bb 也未必是 max{ai}+1max{ai}+1，它可以任意选一个大于 max{ai}+1max{ai}+1 的数。
3.代码实现
```java class Solution { List temp = new ArrayList (); List > ans = new ArrayList >(); Set set = new HashSet (); int n;
1. public List<List<Integer>> findSubsequences(int[] nums) { 2. n = nums.length; 3. for (int i = 0; i < (1 << n); ++i) { 4. findSubsequences(i, nums); 5. int hashValue = getHash(263, (int) 1E9 + 7); 6. if (check() && !set.contains(hashValue)) { 7. ans.add(new ArrayList<Integer>(temp)); 8. set.add(hashValue); 9. } 10. } 11. return ans; 12. } 13. 14. public void findSubsequences(int mask, int[] nums) { 15. temp.clear(); 16. for (int i = 0; i < n; ++i) { 17. if ((mask & 1) != 0) { 18. temp.add(nums[i]); 19. } 20. mask >>= 1; 21. } 22. } 23. 24. public int getHash(int base, int mod) { 25. int hashValue = 0; 26. for (int x : temp) { 27. hashValue = hashValue * base % mod + (x + 101); 28. hashValue %= mod; 29. } 30. return hashValue; 31. } 32. 33. public boolean check() { 34. for (int i = 1; i < temp.size(); ++i) { 35. if (temp.get(i) < temp.get(i - 1)) { 36. return false; 37. } 38. } 39. return temp.size() >= 2; 40. }
}
```
二、Leetcode 46.全排列
1.题目
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1. 1 <= nums.length <= 6 2. -10 <= nums[i] <= 10 3. nums 中的所有整数 互不相同
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/permutations
2.解题思路
方法一：回溯
思路和算法
这个问题可以看作有 nn 个排列成一行的空格，我们需要从左往右依此填入题目给定的 nn 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 nn 个空格，在程序中我们可以用「回溯法」来模拟这个过程。
我们定义递归函数 backtrack(first,output)backtrack(first,output) 表示从左往右填到第 firstfirst 个位置，当前排列为 outputoutput。 那么整个递归函数分为两个情况：
1. 如果 first=nfirst=n，说明我们已经填完了 nn 个位置(注意下标从 00 开始)，找到了一个可行的解，我们将 outputoutput 放入答案数组中，递归结束。 2. 如果 first<nfirst<n，我们要考虑这第 firstfirst 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 visvis 来标记已经填过的数，那么在填第 firstfirst 个数的时候我们遍历题目给定的 nn 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first+1,output)backtrack(first+1,output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。
使用标记数组来处理填过的数是一个很直观的思路，但是可不可以去掉这个标记数组呢？毕竟标记数组也增加了我们算法的空间复杂度。
答案是可以的，我们可以将题目给定的 nn 个数的数组 numsnums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。
具体来说，假设我们已经填到第 firstfirst 个位置，那么 numsnums 数组中 [0,first−1][0,first−1] 是已填过的数的集合，[first,n−1][first,n−1] 是待填的数的集合。我们肯定是尝试用 [first,n−1][first,n−1] 里的数去填第 firstfirst 个数，假设待填的数的下标为 ii，那么填完以后我们将第 ii 个数和第 firstfirst 个数交换，即能使得在填第 first+1first+1 个数的时候 numsnums 数组的 [0,first][0,first] 部分为已填过的数，[first+1,n−1][first+1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作。
举个简单的例子，假设我们有 [2,5,8,9,10][2,5,8,9,10] 这 55 个数要填入，已经填到第 33 个位置，已经填了 [8,9][8,9] 两个数，那么这个数组目前为 [8,9 ∣ 2,5,10][8,9 ∣ 2,5,10] 这样的状态，分隔符区分了左右两个部分。假设这个位置我们要填 1010 这个数，为了维护数组，我们将 22 和 1010 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8,9,10 ∣ 2,5][8,9,10 ∣ 2,5] 。
当然善于思考的读者肯定已经发现这样生成的全排列并不是按字典序存储在答案数组中的，如果题目要求按字典序输出，那么请还是用标记数组或者其他方法。
3.代码实现
```java class Solution { public List > permute(int[] nums) { List > res = new ArrayList >();
1. List<Integer> output = new ArrayList<Integer>(); 2. for (int num : nums) { 3. output.add(num); 4. } 5. 6. int n = nums.length; 7. backtrack(n, output, res, 0); 8. return res; 9. } 10. 11. public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) { 12. // 所有数都填完了 13. if (first == n) { 14. res.add(new ArrayList<Integer>(output)); 15. } 16. for (int i = first; i < n; i++) { 17. // 动态维护数组 18. Collections.swap(output, first, i); 19. // 继续递归填下一个数 20. backtrack(n, output, res, first + 1); 21. // 撤销操作 22. Collections.swap(output, first, i); 23. } 24. }
}
```
三、Leetcode 47.全排列 II
1.题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1. 1 <= nums.length <= 8 2. -10 <= nums[i] <= 10
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/permutations-ii
2.解题思路
方法一：搜索回溯
思路和算法
此题是「46. 全排列」的进阶，序列中包含了重复的数字，要求我们返回不重复的全排列，那么我们依然可以选择使用搜索回溯的方法来做。
我们将这个问题看作有 nn 个排列成一行的空格，我们需要从左往右依次填入题目给定的 nn 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 nn 个空格，在程序中我们可以用「回溯法」来模拟这个过程。
我们定义递归函数 backtrack(idx,perm)backtrack(idx,perm) 表示当前排列为 permperm，下一个待填入的位置是第 idxidx 个位置(下标从 00 开始)。那么整个递归函数分为两个情况：
1. 如果 idx=nidx=n，说明我们已经填完了 nn 个位置，找到了一个可行的解，我们将 permperm 放入答案数组中，递归结束。 2. 如果 idx<nidx<n，我们要考虑第 idxidx 个位置填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 visvis 来标记已经填过的数，那么在填第 idxidx 个数的时候我们遍历题目给定的 nn 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(idx+1,perm)backtrack(idx+1,perm)。搜索回溯的时候要撤销该个位置填的数以及标记，并继续尝试其他没被标记过的数。
但题目解到这里并没有满足「全排列不重复」 的要求，在上述的递归函数中我们会生成大量重复的排列，因为对于第 idxidx 的位置，如果存在重复的数字 ii，我们每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复，因此我们需要处理这个情况。
要解决重复问题，我们只要设定一个规则，保证在填第 idxidx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) { continue; }
这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。
假设我们有 33 个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入][未填入，未填入，未填入] 到 [填入，未填入，未填入][填入，未填入，未填入]，再到 [填入，填入，未填入][填入，填入，未填入]，最后到 [填入，填入，填入][填入，填入，填入] 的过程的，因此可以达到去重的目标。
3.代码实现
```java class Solution { boolean[] vis;
1. public List<List<Integer>> permuteUnique(int[] nums) { 2. List<List<Integer>> ans = new ArrayList<List<Integer>>(); 3. List<Integer> perm = new ArrayList<Integer>(); 4. vis = new boolean[nums.length]; 5. Arrays.sort(nums); 6. backtrack(nums, ans, 0, perm); 7. return ans; 8. } 9. 10. public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) { 11. if (idx == nums.length) { 12. ans.add(new ArrayList<Integer>(perm)); 13. return; 14. } 15. for (int i = 0; i < nums.length; ++i) { 16. if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) { 17. continue; 18. } 19. perm.add(nums[i]); 20. vis[i] = true; 21. backtrack(nums, ans, idx + 1, perm); 22. vis[i] = false; 23. perm.remove(idx); 24. } 25. }
}
```
