491. Non-decreasing Subsequences ⭐
Medium
Given an integer array
nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.Example 1:
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Example 2:
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
Constraints:
1 <= nums.length <= 15-100 <= nums[i] <= 100
func findSubsequences(nums []int) [][]int {
ans := make([][]int, 0)
cur := []int{}
var backtracking func(int)
backtracking = func(index int) {
if len(cur) > 1 {
copyArr := make([]int,len(cur))
copy(copyArr,cur)
ans = append(ans, copyArr)
}
m := make(map[int]bool) //紀錄要加的新的值是不是已經被加過
for i:=index; i<len(nums); i++ {
if m[nums[i]]{
continue
}
last := -101
if len(cur) > 0 { last = cur[len(cur) - 1]}
if nums[i] >= last && !m[nums[i]]{
cur = append(cur,nums[i])
backtracking(i+1)
m[cur[len(cur)-1]] = true
cur = cur[:len(cur)-1]
}
}
}
backtracking(0)
return ans
}
Last modified 4mo ago