代码随想录补|leetcode491

2024-01-03 08:04:18

?这道题和子集Ⅱ问题的共同点是:都是收取过程中的结果。

不同点是:1.本题要求递增子序列中?至少有两个元素

? ? ? ? ? ? ? ? ? 2.本题是要按数组原本的顺序求子序列,因此不能sort数组,不能用子集问题的used数组方式去重

注意set集合在每一层去重,是横着去重的。每次回溯都有生成一个新的set集合,就不会影响竖着的。这也是和used数组去重不同的地方。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return result;
    }
    public void backtracking(int[] nums,int startIndex){
        Set<Integer> used = new HashSet<>();
        if(list.size() >= 2){
            result.add(new ArrayList<>(list));
        }
        if(startIndex == nums.length){
            return;
        }
        for(int i = startIndex;i<nums.length;i++){
            if(!list.isEmpty() && nums[i] < list.get(list.size() - 1) || used.contains(nums[i])){
            continue;
            }else{
                list.add(nums[i]);
                used.add(nums[i]);
                backtracking(nums,i+1);
                list.remove(list.size() - 1);
            }
        }
    }
}

文章来源:https://blog.csdn.net/l82049/article/details/135286837
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。