491. Increasing subsequence
Given an array of integers, nums, find and return all the different incrementing subsequences of that array that have at least two elements. You can return the answers in any order.
An array may contain duplicate elements. If two integers are equal, this can also be considered a special case of increasing sequences.
Example 1
Output: input: nums =,6,7,7 [4], [[4, 6], [4, 6], [4,6,7,7], [4, 7], [4,7,7], [6, 7], [6,7,7], [7, 7]]Copy the code
Example 2
Nums = [4,4,3,2,1] output: [[4,4]]Copy the code
solution
func findSubsequences(nums []int)[] []int {
res:=[][]int{}
dfs(nums,0.nil,&res)
return res
}
func dfs(nums []int, index int,temp []int, res *[][]int){
if len(temp)>1{
copyTemp:=make([]int.len(temp))
copy(copyTemp,temp)
*res=append(*res,copyTemp)
}
hashMap:=map[int]bool{}
fori:=index; i<len(nums); i++{ curTempLen:=len(temp)
if curTempLen>=1 && nums[i]<temp[curTempLen- 1] || hashMap[nums[i]]{
continue
}
hashMap[nums[i]]=true
dfs491(nums,i+1.append(temp,nums[i]),res)
}
}
Copy the code