AlgoPressAppearance
0491-递增子序列
https://leetcode.cn/problems/increasing-subsequences 给你一个整数数组 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 <= nums.length <= 15
-100 <= nums[i] <= 100
思路
回溯法，递归遍历数组，当发现小于前一个数字的时候退出。
参考代码:有出错
测试案例： [1,2,1,1] 会出错。 输出： [[1,2],[1,1],[1,1,1],[1,1]] 预期结果 : [[1,2],[1,1],[1,1,1]]
其原因是，当递归到第三个1的时候，可以和第四个1组成 1,1 但是这个结果和 第一个1，第三个1组成的重复了。
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private bool[] used ;
private void dfs(int[] nums, int startIndex, List<int> list){
if(list.Count >= 2){
if(list[list.Count - 1] < list[list.Count -2]){
return;
}
result.Add(new List<int>(list.ToArray()));
}
//组合问题，从startIndex开始
for(int i=startIndex; i<nums.Length; i++){
if(i>0 && nums[i] == nums[i-1] && !used[i-1] ){
continue;
}
list.Add(nums[i]);
used[i] = true;
dfs(nums,i+1,list);
list.RemoveAt(list.Count-1);
used[i] = false;
}
}
public IList<IList<int>> FindSubsequences(int[] nums) {
List<int> list = new List<int>();
used = new bool[nums.Length];
dfs(nums,0,list);
return result;
}
}
所以这里， 选取第一个1和第三个1 和第四个1 组成的时候， 前要后不要，和 前不要后要 造成了重复，我们需要做的就是在这里里面只保留一种情况。 前要后不要(相同值只取前面的)
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int[] nums, int begin, List<int> list){
if(begin == nums.Length){
if(list.Count >=2 ){
result.Add(new List<int>(list.ToArray()));
}
return;
}
//选他(当后面的数字大于等于前面的数字才有意义)
if(list.Count == 0 || nums[begin] >= list[list.Count-1]){
list.Add(nums[begin]);
dfs(nums,begin+1, list);
list.RemoveAt(list.Count-1);
}
//不选他
if(list.Count == 0 || nums[begin] != list[list.Count-1] ){
dfs(nums,begin+1, list);
}
}
public IList<IList<int>> FindSubsequences(int[] nums) {
List<int> list = new List<int>();
dfs(nums,0,list);
return result;
}
}
参考代码2:官方
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int[] nums, int startIndex, int last, List<int> list){
if(startIndex == nums.Length){
if(list.Count >=2 ){
result.Add(new List<int>(list.ToArray()));
}
return;
}
//选他(当后面的数字大于前面的数字才有意义)
if(nums[startIndex] >= last){
list.Add(nums[startIndex]);
dfs(nums,startIndex+1, nums[startIndex], list);
list.RemoveAt(list.Count-1);
}
//不选他
if(nums[startIndex] != last){
dfs(nums,startIndex+1,last, list);
}
}
public IList<IList<int>> FindSubsequences(int[] nums) {
List<int> list = new List<int>();
dfs(nums,0,int.MinValue, list);
return result;
}
}