🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 491. Non-decreasing Subsequences
Сложность: medium
Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.
Пример:
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]]
👨💻 Алгоритм:
1⃣Инициализация и запуск функции обратного отслеживания
Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0.
2⃣Функция обратного отслеживания
Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента.
3⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.
😎 Решение:
public class Solution {
public IList FindSubsequences(int[] nums) {
var result = new HashSet();
var sequence = new List();
Backtrack(nums, 0, sequence, result);
return result.ToList();
}
private void Backtrack(int[] nums, int index, List sequence, HashSet result) {
if (index == nums.Length) {
if (sequence.Count >= 2) {
result.Add(new List(sequence));
}
return;
}
if (sequence.Count == 0 || sequence[sequence.Count - 1]