Этот код использует алгоритм поиска в глубину (dfs), чтобы найти все различные возможные неубывающие подпоследовательности данного массива. Функция dfs начинает с проверки, содержит ли текущая подпоследовательность хотя бы два элемента, и, если да, добавляет ее к результатам. Затем он использует unordered_set для отслеживания элементов, которые использовались в текущей подпоследовательности, и использует цикл for для перебора оставшихся элементов в массиве. Если текущий элемент больше или равен последнему элементу в текущей подпоследовательности, он добавляет элемент в подпоследовательность и рекурсивно вызывает функцию dfs с обновленной подпоследовательностью и начальным индексом. После возврата функция dfs удаляет последний элемент из текущей подпоследовательности.
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
dfs(nums, 0, cur, res);
return res;
}
void dfs(vector<int>& nums, int start, vector<int>& cur, vector<vector<int>>& res)
{
if (cur.size() >= 2) res.push_back(cur);
unordered_set<int> used;
for (int i = start; i < nums.size(); i++) {
if (used.count(nums[i])) continue;
if (cur.empty() || nums[i] >= cur.back()) {
used.insert(nums[i]);
cur.push_back(nums[i]);
dfs(nums, i + 1, cur, res);
cur.pop_back();
}
}
}
Причина этого в том, что для каждого элемента входного массива мы можем либо включать его в текущую подпоследовательность, либо не включать. Это означает, что для массива размера n у нас есть 2^n возможных подпоследовательностей. Затем для каждой из этих возможных подпоследовательностей нам нужно проверить, является ли она неубывающей и имеет ли хотя бы два элемента, что занимает O(n) времени. Следовательно, общая временная сложность составляет O (2 ^ n * n).
Объемная сложность этого решения равна O(n), где n — длина входного массива. Причина этого в том, что мы используем рекурсивный подход для поиска всех возможных подпоследовательностей, который имеет пространственную сложность O(n) из-за стека вызовов. Дополнительное пространство используется из-за вектора, unordered_set и массива, используемых в решении. Это тоже O(n).
