Leetcode 491.递增子序列

力扣传送门(opens new window)

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]]

说明:

• 给定数组的长度不会超过15。
• 数组中的整数范围是 [-100,100]。
• 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

解题思路：

今天我们来讲解 "非递减子序列"（Find All Non-Decreasing Subsequences）。

首先，我们来理解一下题目的要求。给定一个整数数组 nums，我们需要找出所有不同的非递减子序列。非递减子序列是指在原数组中保持相对顺序的子序列，其中相同的元素也可以被视为一个递增子序列。而且，我们要求找出的子序列至少包含两个元素。

那么，我们应该如何解决这个问题呢？我们可以使用回溯算法来求解。回溯算法是一种通过搜索所有可能的解来求解问题的算法。

我们可以定义一个辅助函数，用于递归生成非递减子序列。这个辅助函数的参数包括当前位置 index、当前正在构建的子序列 list、原始数组 nums，以及用于存储结果的集合 res。

在辅助函数中，首先判断当前构建的子序列 list 是否满足条件（至少包含两个元素）。如果满足条件，则将其加入结果集合 res。

接下来，我们从当前位置 index 开始，遍历数组 nums，并进行以下操作：

• 如果当前元素小于 list 的最后一个元素，说明不满足递增的条件，直接跳过该元素。
• 否则，将当前元素加入到子序列 list 中，并递归调用辅助函数，将 index 设置为当前位置的下一个位置。
• 在递归调用结束后，需要将当前元素从子序列 list 中移除，以便尝试其他可能的子序列。

最后，返回结果集合 res，即为所有不同的非递减子序列。

代码实现：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
  
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums == null || nums.length == 0) {
            return res;
        }
  
        LinkedList<Integer> list = new LinkedList<>();
        backTracking(nums, 0, list);
  
        return res;
    }
  
    public void backTracking(int[] nums, int index, LinkedList<Integer> list) {
        if (list.size() > 1) {
            res.add(new ArrayList<>(list));
        }
  
        HashSet<Integer> set = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            if (!list.isEmpty() && nums[i] < list.getLast()) {
                continue;
            }
    
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
                list.add(nums[i]);
                backTracking(nums, i + 1, list);
                list.removeLast();
            }
        }
    }
}