力扣491 非递减子序列 Java版本

本文主要是介绍力扣491 非递减子序列 Java版本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目描述
代码

题目描述

给你一个整数数组 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

代码

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}//使用回溯的方法public void backTracking(int[] nums, int startIndex) {if (path.size() >= 2) {if ((path.get(path.size() - 1)) < (path.get(path.size() - 2))) {return;}result.add(new ArrayList<>(path));}HashSet<Object> set = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {//注意：不能使用下面这种去重的方式，因为这个数组不是递增的数组，所以不能通过连续相同来判断是否要去重//真确的方法是要使用数组或者set或者map来记录是否已经在树的同一层中使用过该数字//if (i > startIndex && nums[i] == nums[i - 1]) {//    continue;//}if (set.contains(nums[i])){continue;}set.add(nums[i]);path.add(nums[i]);backTracking(nums, i + 1);path.removeLast();//回溯}}
}