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