递增子序列

Category	Difficulty	Likes	Dislikes
algorithms	Medium (53.91%)	391	-

Tags

depth-first-search

Companies

yahoo

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

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

示例 1：

1
2
输入：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：

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

提示：

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

Discussion | Solution

解法

 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
27
28
29
30
31
32
33
34
35
36
37
38
// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - dfs
    pub fn find_subsequences(nums: Vec<i32>) -> Vec<Vec<i32>> {
        use std::collections::HashSet;
        fn dfs(nums: &[i32], start: usize, inc_nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
            if start == nums.len() {
                return;
            }
            let mut level_used = HashSet::new();
            for j in start..nums.len() {
                // 排除重复的数字
                if j > start && nums[j] == nums[j - 1] || level_used.contains(&nums[j]) {
                    continue;
                }
                if inc_nums.len() == 0 || nums[j] >= *inc_nums.last().unwrap() {
                    level_used.insert(nums[j]);
                    inc_nums.push(nums[j]);
                    if inc_nums.len() > 1 {
                        res.push(inc_nums.clone());
                    }
                    dfs(nums, j + 1, inc_nums, res);
                    inc_nums.pop();
                }
            }
        }

        let mut res = vec![];
        let mut inc_nums = vec![];
        dfs(&nums, 0, &mut inc_nums, &mut res);

        res
    }
}
// @lc code=end
struct Solution;

递增子序列

递增子序列

解法

相关文章：