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
}