LeetCode_回溯_中等_491.递增子序列

x33g5p2x  于2022-08-17 转载在 其他  
字(1.0k)|赞(0)|评价(0)|浏览(342)

1.题目

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/increasing-subsequences

2.思路

(1)回溯
思路参考本题官方题解

3.代码实现(Java)

//思路1————回溯
class Solution {
    
    // res 保存所有结果
    List<List<Integer>> res = new ArrayList<>();
    
    // track 用于记录回溯的路径
    List<Integer> track = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length <= 1) {
            return res;
        }
        backtrack(nums, 0, Integer.MIN_VALUE);
        return res;
    }
    
    public void backtrack(int[] nums, int cur, int last) {
        //找到一组递增子序列
        if (cur == nums.length) {
            if (track.size() >= 2) {
                res.add(new ArrayList<Integer>(track));
            }
            return;
        }
        if (nums[cur] >= last) {
            track.add(nums[cur]);
            backtrack(nums, cur + 1,nums[cur]);
            track.remove(track.size() - 1);
        }
        if (nums[cur] != last) {
            backtrack(nums, cur + 1, last);
        }
    }
}

相关文章

微信公众号

最新文章

更多