vector find 递增子序列问题：与子集问题相似但又有诸多陷阱

vector find 递增子序列问题：与子集问题相似但又有诸多陷阱

这有点像子集问题，但它充满了陷阱。

注：我将公众号文章和学习相关资料整理成：，方便大家在电脑上学习。你可以fork到你自己的仓库。对了，还可以给个star支持一下！

491.增加子序列

问题链接：

给定一个整数数组，您的任务是找到该数组中长度至少为 2 的所有递增子序列。

例子：

输入：[4, 6, 7, 7] 输出：[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6,7,7],[7,7],[4,7,7]]

阐明：

想法

这个递增子序列更像是采用有序子集。而且，这题还要求不能有相同的递增子序列。

这是子集和重复数据删除。你是否不由自主地想到了刚才提到的回溯算法：子集问题（2）。

正因为它们如此相似，所以你必须更加注意差异，否则你就会陷入陷阱！

在回溯算法：子集问题（2）中，我们通过排序和添加标记数组来达到去重的目的。

至于本题中的自增子序列，原数组无法排序。排序后的数组都是自增子序列。

“所以不能使用之前的去重逻辑！”

本题给出的例子仍然是有序数组[4,6,7,7]，这更容易误导大家遵循排序思想。

为了有一个清晰的对比，我以数组[4,7,6,7]为例，将其抽象成树形结构如图：

回顾三部曲

这个问题需要一个子序列。显然，一个元素是不能被重用的，所以需要调整下一级递归的起始位置。

代码如下：

vector> result;
vector path;
void backtracking(vector& nums, int startIndex) 

这个问题其实和寻找子集的问题类似。它也需要遍历树结构来找到每个节点，所以它类似于回溯算法：寻找子集的问题！同样，不需要添加终止条件，每次都会加1，不会无限递归。

不过，这道题的采集结果却有所不同。题目要求增量子序列大小至少为2，所以代码如下：

if (path.size() > 1) {
    result.push_back(path);
    // 注意这里不要加return，因为要取树上的所有节点
}

从图中可以看出，同一层上已经使用过的元素不能再使用了。 “注意这个和回溯算法的区别：找到子集问题（2）去除重复。”

“在这道题中，只要在同一层重用元素，增量子序列就会重复。”在回溯算法：子集问题（2）中，我们检查排序后相邻元素是否被重用。

另一种情况是，如果选择的元素比子序列的最后一个元素小，则不能增量，所以必须通过。

那么去重的逻辑代码如下：

if ((!path.empty() && nums[i] < path.back())
        || uset.find(nums[i]) != uset.end()) {
        continue;
}

在判断nums[i] < path.back()之前，必须先判断path是否为空，所以!path.empty() && nums[i] < path.back()。

uset.find(nums[i]) != uset.end() 判断nums[i]是否已经在本层使用过。

那么单层搜索代码如下：

unordered_set uset; // 使用set来对本层元素进行去重
for (int i = startIndex; i < nums.size(); i++) {
    if ((!path.empty() && nums[i] < path.back())
            || uset.find(nums[i]) != uset.end()) {
            continue;
    }
    uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
    path.push_back(nums[i]);
    backtracking(nums, i + 1);
    path.pop_back();
}

“对于习惯写的同学来说，看到递归函数上的uset.(nums[i]);可能会不太习惯，但并没有像下面的pop这样的对应操作，哈哈。”

“这也是需要注意的一点，uset;记录了本层的元素是否被复用，新的uset层会被重新定义（清除），所以你要知道uset只负责这一层！”

最终整体C++代码如下：

C++代码

// 版本一
class Solution {
private:
    vector> result;
    vector path;
    void backtracking(vector& nums, int startIndex) {
        if (path.size() > 1) {
            result.push_back(path);
            // 注意这里不要加return，要取树上的节点
        }
        unordered_set uset; // 使用set对本层元素进行去重
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back())
                    || uset.find(nums[i]) != uset.end()) {
                    continue;
            }
            uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector> findSubsequences(vector& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

优化

我用上面的代码来记录这一层的元素是否被重用。

“事实上，使用数组进行哈希处理效率要高得多。”

请注意，问题说数值范围是[-100,100]，因此可以使用数组进行散列。

程序运行时，哈希映射（即通过哈希将键映射到唯一的哈希值）是比较耗时的，而且每次重新定义集合时，底层的符号表也必须进行相应的修改。扩容也很麻烦。

那么优化后的代码如下：

// 版本二
class Solution {
private:
    vector> result;
    vector path;
    void backtracking(vector& nums, int startIndex) {
        if (path.size() > 1) {
            result.push_back(path);
        }
        int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back())
                    || used[nums[i] + 100] == 1) {
                    continue;
            }
            used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector> findSubsequences(vector& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

提交此代码比版本一要耗时得多。

”所以正如互联网公司面试题的哈希表总结中所说！（每一篇总结都必须经典），数组、集合、映射都可以用来制作哈希表，而数组所做的工作可以通过map和set来完成，但是如果数值范围较小，可以使用数组，尽量使用数组。”

总结

这道题的所有答案都说是深度优先搜索，但我更倾向于说是用回溯法，而且我也完全用了回溯法的逻辑来分析这道题。

相信你在这道题中处处都能看到回溯算法：子集问题(2)，但处处都是陷阱。

“这个问题对于那些已经形成固定型思维或者沉迷于模板的同学来说，是一个很好的警钟。更重要的是，它拓展了大家的思维！”