491. Non-decreasing Subsequences

Level - medium

Task

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.

Объяснение

Необходимо найти все неубывающие подпоследовательности в заданном массиве целых чисел. Подпоследовательность — это последовательность, которая может быть получена из исходной последовательности путем удаления некоторых элементов (или ни одного) без изменения порядка оставшихся элементов. Неубывающая подпоследовательность — это такая подпоследовательность, в которой каждый элемент больше или равен предыдущему элементу.

Пошаговый разбор:

1. Понимание задачи. Нам нужно сгенерировать все возможные подпоследовательности заданного массива и отфильтровать те, которые являются неубывающими.

2. Генерация подпоследовательностей. Мы можем сгенерировать все подпоследовательности с помощью рекурсивного подхода или итеративного подхода с использованием бэктрекинга (обратного отслеживания).

3. Проверка на неубывание. Для каждой сгенерированной подпоследовательности проверяем, является ли она неубывающей.

4. Хранение допустимых подпоследовательностей. Сохраняем все подпоследовательности, которые удовлетворяют критерию неубывания.

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