Сложность: 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⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.
😎 Решение:
class Solution {
func findSubsequences(_ nums: [Int]) -> [[Int]] {
var result = Set<[Int]>()
var sequence = [Int]()
backtrack(nums, 0, &sequence, &result)
return Array(result)
}
func backtrack(_ nums: [Int], _ index: Int, _ sequence: inout [Int], _ result: inout Set<[Int]>) {
if index == nums.count {
if sequence.count >= 2 {
result.insert(sequence)
}
return
}
if sequence.isEmpty || sequence.last! <= nums[index] {
sequence.append(nums[index])
backtrack(nums, index + 1, &sequence, &result)
sequence.removeLast()
}
backtrack(nums, index + 1, &sequence, &result)
}
}Ставь 👍 и забирай 📚 Базу знаний