资讯专栏INFORMATION COLUMN

leetcode78. Subsets

Rocko / 1232人阅读

摘要:题目要求类似的题目有可以参考这篇博客可以参考这篇博客思路一递归还是利用递归的方式,在前一种情况的基础上遍历下一轮的组合情况。

题目要求
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

类似的题目有:
leetcode60 Permutation Sequence 可以参考这篇博客
leetcode77 Combinations 可以参考这篇博客

思路一:递归

还是利用递归的方式,在前一种情况的基础上遍历下一轮的组合情况。

    public List> subsets(int[] nums) {
        List> result = new ArrayList>();
        result.add(new ArrayList());
        subsets(result, nums, 0, new ArrayList());
        return result;
    }
    
    public void subsets(List> result, int[] nums, int startIndex, List currentList){
        if(startIndex == nums.length){
            return;
        }
        while(startIndex(currentList));
            subsets(result, nums, startIndex, currentList);
            currentList.remove(currentList.size()-1);
        }
    }
思路2:排序后循环

起始subset集为:[]
添加S0后为:[], [S0]
添加S1后为:[], [S0], [S1], [S0, S1]
添加S2后为:[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]

public List> subsets(int[] S) {
    List> res = new ArrayList<>();
    res.add(new ArrayList());
    
    for(int i : S) {
        List> tmp = new ArrayList<>();
        for(List sub : res) {
            List a = new ArrayList<>(sub);
            a.add(i);
            tmp.add(a);
        }
        res.addAll(tmp);
    }
    return res;
}


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67306.html

相关文章

  • leetcode-78-Subsets

    摘要:描述解释就是普通的动态规划吧,找准规律,所有数字过一遍,每个数字都有添加和不被添加两种情况,所有情况的综合 描述 Given a set of distinct integers, nums, return all possible subsets(the power set). Note: The solution set must not contain duplicate sub...

    dockerclub 评论0 收藏0
  • Leetcode78. 子集

    摘要:题目给定一组不含重复元素的整数数组,返回该数组所有可能的子集幂集。说明解集不能包含重复的子集。示例输入输出题解全排列,部分排列这些问题都是回溯的题目。这个题目每个状态都是解,包括空也是解,所以直接都加进去就好。 题目 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ ...

    laznrbfe 评论0 收藏0
  • Leetcode78. 子集

    摘要:题目给定一组不含重复元素的整数数组,返回该数组所有可能的子集幂集。说明解集不能包含重复的子集。示例输入输出题解全排列,部分排列这些问题都是回溯的题目。这个题目每个状态都是解,包括空也是解,所以直接都加进去就好。 题目 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ ...

    miqt 评论0 收藏0
  • LeetCode 子集合,排列组合,回文分离等问题的通用递归算法

    摘要:通用算法思路总结初始结果列表。可能要将数集排序,方便处理重复元素的情况。书写递归函数,先要考虑原点状况,一般就是考虑什么情况下要将当前结果添加到结果列表中。每当一个元素添加到当前结果中之后,要再调用递归函数,相当于固定了前缀穷举后面的变化。 通用算法思路总结: 初始结果列表。 可能要将数集排序,方便处理重复元素的情况。 调用递归函数。 书写递归函数,先要考虑原点状况,一般就是考虑什么...

    cfanr 评论0 收藏0
  • LeetCode 关于回溯问题的看法

    摘要:回溯算法在算法过程中就是类似于枚举算法,尝试在搜索过程中找到问题的解。 回溯算法( BackTrack )在算法过程中就是类似于枚举算法,尝试在搜索过程中找到问题的解。 使用回溯算法解题的一般步骤 使用回溯算法解题的一般步骤: 针对所给问题得出一般的解空间 用回溯搜索方法搜索解空间 使用深度优先去搜索所有解并包含适当的剪枝操作 LeetCode 使用回溯算法的题目主要有 36 题,...

    ASCH 评论0 收藏0

发表评论

0条评论

Rocko

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<