Задача: Неубывающий подмассив

Условие: дается целочисленный массив nums, верните все различные возможные неубывающие подпоследовательности данного массива, по крайней мере, с двумя элементами. Вы можете вернуть ответ в любом порядке.

Пример:

Ввод: 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]]

Ввод: nums = [4,4,3,2,1]

Вывод: [[4,4]]

Решение:

func findSubsequences(nums []int) [][]int {
    var output = make([][]int, 0)
    var tmp = make([]int, 0)
    dfs(0, nums, &output, &tmp)
    return output
}

func dfs(start int, nums []int, output *[][]int, tmp *[]int) {
    if len(*tmp) >= 2 {
        cp := make([]int, len(*tmp))
        copy(cp, *tmp)
        *output = append(*output, cp)
    }

    var visited = make(map[int]bool)
    for i := start; i < len(nums); i++ {
        if (len(*tmp) > 0 && (*tmp)[len(*tmp)-1] > nums[i]) || visited[nums[i]]{
            continue
        }
        *tmp = append(*tmp, nums[i])
        visited[nums[i]] = true
        dfs(i+1, nums, output, tmp)
        *tmp = (*tmp)[:len(*tmp)-1]
    }
}

Сложность

Временная сложность: O(2n)O(2^n)O(2 n )

Пространственная сложность: O(2n)O(2^n)O(2 n)