LeetCode 491. Increasing Subsequences

Posted on | In | |

题目描述

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

  1. The length of the given array will not exceed 15.
  2. The range of integer in the given array is [-100,100].
  3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

题目大意是：从给定的一组数中，找到所有递增的子序列。但其实这里的递增（increasing）包含了所有非递减的子序列，从样例中可知。还有一点需要注意的是，题目给定的一组数（vector<int> nums）其实是有序的，即不能通过改变nums中的数的顺序来获取递增的子序列。虽然这一点在题目中没有明确说明，但是评测中会有这么一个样例：

Input: [4,3,2,1]
Output: []

因此，在实现时还要注意保持nums中数列的顺序。

算法分析

考虑用dfs的递归实现。主要的问题在于如何解决冗余。例如：输入为[1, 3, 3, 3, 5]单纯的dfs可能会得到重复的[1, 3], [3, 3], [3, 5]等。解决的思路也很简单，由于子序列都是递增的，那么在dfs过程中只保留重复数字的第一位即可。因为，第一个重复数字所能与后面的数列得到的递增子序列，一定是所有重复数字中最多的。因此，在dfs中增加一个bool exist[]即可解决。

代码实现

C++代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
void dfs(vector<vector<int>> &result, vector<int> &nums, int startIndex, vector<int> &curVec) {
    if (curVec.size() >= 2) {
        result.push_back(curVec);
    }
    bool exist[201] = { false };  // 因为题目中数字范围为[-100,100]
    for (int index = startIndex; index < nums.size(); index++) {
        if ((curVec.empty() || nums[index] >= curVec.back()) && exist[nums[index] + 100] == false) {
            exist[nums[index] + 100] = true;  // 标记以去除冗余
            curVec.push_back(nums[index]);
            dfs(result, nums, index + 1, curVec);
            curVec.pop_back();  // dfs中的回溯
        }
    }
}

vector<vector<int>> findSubsequences(vector<int>& nums) {

    vector<vector<int>> result;
    vector<int> curVec;
    dfs(result, nums, 0, curVec);

    return result;
}
};

本文为博主原创文章，转载请注明出处。