【LetMeFly】491.递增子序列：两大方法三小方法

力扣题目链接：https://leetcode.cn/problems/increasing-subsequences/

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

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

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

1 <= nums.length <= 15
-100 <= nums[i] <= 100

方法一：二进制枚举

二进制枚举每一种子序列，然后判断这个子序列是否合法，如果合法就添加到答案中

其中二进制的每一位对应原始数组中的一个元素，这一位为0则不取这个元素，否则取这个元素。

主要答案需要去重，可以使用自带哈希表

时间复杂度 $O(2^n\times n)$ ，二进制枚举的时间复杂度是 $2^n$ ；哈希表中最大元素个数为 $2^n$ ，此时一次插入的时间复杂度是 $\log 2^n=n\times log2\to n$
空间复杂度 $O(2^n)$

AC代码

C++

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // unordered_set<vector<int>, VectorHash, VectorEqual> se;
        set<vector<int>> se;
        int n = nums.size(), to = 1 << n;
        for (int i = 0; i < to; i++) {
            int last = -100;
            vector<int> thisV;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    if (nums[j] < last)
                        goto loop;
                    thisV.push_back(nums[j]);
                    last = nums[j];
                }
            }
            if (thisV.size() > 1)
                se.insert(thisV);
            loop:;
        }
        vector<vector<int>> ans;
        for (auto& v : se)
            ans.push_back(v);
        return ans;
    }
};

方法一.2：针对方法一中哈希表的优化

与方法一相比，我们使用 $unordered_set$ ，这样插入的效率会变高。

但是 $C + +$ 的 $ST L$ 默认没有 $v ec t or$ 的哈希函数，需要我们自定义 $v ec t or$ 的哈希函数或者将 $v ec t or$ 映射为整数，同时将整数映射为 $v ec t or$

具体映射方法为：

因为vector中每个数的取值范围是 $[? 100, 100]$ ，所以我们可以将每个数加上 $100$ ，这样每个数的取值范围就是 $[1, 201]$ 一共 $201$ 种。使用无符号整数每次乘以 $201$ 后加上新的数自然溢出，发现对于力扣此题没有产生哈希冲突。

时间复杂度 $O(2^n\times n)$ ，unordered_set的插入时间复杂度是 $O (1)$ ，但是需要遍历最大长度为 $n$ 的数组来求得哈希值
空间复杂度 $O(2^n)$

AC代码

C++

class Solution {
private:
    unordered_map<unsigned, vector<int>> ma;

    unsigned hash(vector<int>& v) {
        unsigned ans = 0;  // 32位无符号整数自然溢出
        for (int& t : v) {
            ans = ans * 201 + (t + 101);  // t + 101 -> [1, 201]  // +100不可以！！！会冲突  // 如果+100的话，[-100, 5]和[5]都会是105
        }
        ma[ans] = v;
        return ans;
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // unordered_set<vector<int>, VectorHash, VectorEqual> se;
        unordered_set<int> se;
        int n = nums.size(), to = 1 << n;
        for (int i = 0; i < to; i++) {
            int last = -100;
            vector<int> thisV;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    if (nums[j] < last)
                        goto loop;
                    thisV.push_back(nums[j]);
                    last = nums[j];
                }
            }
            if (thisV.size() > 1)
                se.insert(hash(thisV));
            loop:;
        }
        vector<vector<int>> ans;
        for (auto& t : se)
            ans.push_back(ma[t]);
        return ans;
    }
};

方法三：深度优先搜索DFS

我们用函数dfs(nums, loc, lastNum)来计算 $n u m s$ 数组从 $l oc$ 开始，上一个数是 $l a s tN u m$ 的所有可行方案

用一个临时数组 $t e m p$ 来存放当前方案

如果 $l oc == n u m s . s i ze ()$ （已经超出有效范围了），那么就看 $t e m p$ 中存放的方案是否合法（至少两个数），如果合法就添加到答案中。

如果 $l oc < n u m s . s i ze ()$ ，那么就有“选nums[loc]”和“不选nums[loc]”两种方案。“选nums[loc]”的前提是 $n u m s [l oc] >= l a s tN u m$ 。

如果选择 $n u m s [l oc]$ ，那么就将 $n u m s [l oc]$ 添加到临时数组中，递归深搜，返回时再将其从临时数组的末尾移除。

如果不选择 $n u m s [l oc]$ ，那么当且仅当 $\neq lastNum$ 时才进行深搜，因为前面的 $l a s tN u m$ 和 $n u m s [l oc]$ 相等，所以“选了lastNum不选nums[loc]”和“选了nums[loc]不选lastNum”是等价的，不选择 $n u m s [l oc]$ 而仍然递归深搜会导致答案重复。

时间复杂度 $O(2^n\times n)$
空间复杂度 $O (n)$ ，临时数组和递归消耗的空间复杂度都是 $(n)$

虽然时间复杂度看似和方法一相同，但实际执行效率还是要高一些。

AC代码

C++

class Solution {
private:
    unordered_map<unsigned, vector<int>> ma;

    unsigned hash(vector<int>& v) {
        unsigned ans = 0;  // 32位无符号整数自然溢出
        for (int& t : v) {
            ans = ans * 201 + (t + 101);  // t + 101 -> [1, 201]  // +100不可以！！！会冲突  // 如果+100的话，[-100, 5]和[5]都会是105
        }
        ma[ans] = v;
        return ans;
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // unordered_set<vector<int>, VectorHash, VectorEqual> se;
        unordered_set<int> se;
        int n = nums.size(), to = 1 << n;
        for (int i = 0; i < to; i++) {
            int last = -100;
            vector<int> thisV;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    if (nums[j] < last)
                        goto loop;
                    thisV.push_back(nums[j]);
                    last = nums[j];
                }
            }
            if (thisV.size() > 1)
                se.insert(hash(thisV));
            loop:;
        }
        vector<vector<int>> ans;
        for (auto& t : se)
            ans.push_back(ma[t]);
        return ans;
    }
};