代码随想录算法训练营第29天| 491.递增子序列 46.全排列 47.全排列 II

**代码随想录算法训练营第29天**

今天，我们将讨论三个经典的算法题目：491.递增子序列、46.全排列和47.全排列 II。

###1. 递增子序列（491）

给定一个整数数组 `nums`，请找出所有可能的递增子序列。注意，每个递增子序列都应该尽可能地长，但不能包含任何数字超过两次。如果某个元素在原数组中出现次数多于2 次，则该元素将无法出现在答案中。

**示例：**

* 输入:`nums = [1,1,2]`
* 输出:`[[1,2],[1,1,2]]`

#### 解决方案：

class Solution:
 def findSubsequences(self, nums: List[int]) -> List[List[int]]:
 res = set()
 def dfs(i, path):
 if i == len(nums) or (len(path) >1 and path[-1] < nums[i]):
 if len(path) >1:
 res.add(tuple(sorted(path)))
 return dfs(i +1, path)
 dfs(i +1, path + [nums[i]])
 dfs(0, [])
 return [list(x) for x in res]

###2. 全排列（46）

给定一个非空整数数组 `nums`，请找出所有可能的全排列。注意，每个解都应该是唯一的，不同的答案不能有重复。

**示例：**

* 输入:`nums = [1,2,3]`
* 输出:`[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`

#### 解决方案：

class Solution:
 def permute(self, nums: List[int]) -> List[List[int]]:
 res = []
 def dfs(nums):
 if len(nums) ==1:
 res.append(nums[:])
 return for i in range(len(nums)):
 new_nums = nums[:i] + nums[i+1:]
 dfs(new_nums)
 for j in range(len(res)):
 res[j].insert(0, nums[i])
 dfs(nums)
 return res

###3. 全排列 II（47）

给定一个集合 `nums`，包含从1 到 n 的 n 个元素（n >=1）。请找出所有可能的全排列。每个解都应该是唯一的，不同的答案不能有重复。

**示例：**

* 输入:`nums = [1,2,3]`
* 输出:`[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`

#### 解决方案：

class Solution:
 def permuteUnique(self, nums: List[int]) -> List[List[int]]:
 res = []
 def dfs(nums):
 if len(nums) ==1:
 res.append(nums[:])
 return for i in range(len(nums)):
 new_nums = nums[:i] + nums[i+1:]
 dfs(new_nums)
 for j in range(len(res)):
 res[j].insert(0, nums[i])
 dfs(sorted(nums))
 return res

以上就是今天的内容。我们讨论了三个经典的算法题目：递增子序列、全排列和全排列 II。这些问题都涉及到对给定数据进行排序或重新排列，以满足特定的条件。通过使用深度优先搜索（DFS）和其他算法技巧，我们可以有效地解决这些问题并得到正确的答案。

如果你有任何问题或者想讨论更多关于这些主题的内容，请随时告诉我！