【Leetcode】78. 子集

miqt 发布于2019-07-30 17:56 / 2768人阅读

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

题目

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题解

全排列，部分排列这些问题都是回溯的题目。这个题目每个状态都是解，包括空list也是解，所以直接都加进去就好。

java

class Solution {
    public List> subsets(int[] nums) {
        List> list = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }

    private void backtrack(List> list, List tempList, int[] nums, int start) {
        list.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

python

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        list = []
        nums.sort()
        self.bracktrack(list, [], nums, 0)
        return list

    def bracktrack(self, list, tempList, nums, start):
        list.append(tempList.copy())
        for i in range(start, len(nums)):
            tempList.append(nums[i])
            self.bracktrack(list, tempList, nums, i + 1)
            tempList.pop()

回溯题目汇总

【Leetcode】77. 组合

【Leetcode】60. 第k个排列

【Leetcode】47. 全排列 II

【Leetcode】46.全排列

服务器托管专线服务子集 a78 php 78E LeetCode

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

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

【Leetcode】78. 子集

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

laznrbfe 2019-08-19 11:15 评论0 收藏0
「leetcode」78.子集

摘要：原题给定一组不含重复元素的整数数组，返回该数组所有可能的子集幂集。说明解集不能包含重复的子集。示例输入输出思路使用位移和按位与的思路，来自的评论区。这个思路相对来说比较抽象，下面是具体的解释。 showImg(https://segmentfault.com/img/remote/1460000020181883); 原题给定一组不含重复元素的整数数组 nums，返回该数组所有可能的...

liuhh 2019-08-26 11:00 评论0 收藏0
力扣(LeetCode)78

摘要：题目地址题目描述给定一组不含重复元素的整数数组，返回该数组所有可能的子集幂集。说明解集不能包含重复的子集。示例输入输出解答这一题用回溯法。对于长度为的数组，它的解空间应该是这样的这里的或者，代表第个数放或者不放入子集。题目地址：https://leetcode-cn.com/probl...题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：...

rollback 2019-08-16 15:17 评论0 收藏0
LeetCode 子集合，排列组合，回文分离等问题的通用递归算法

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

cfanr 2019-08-14 15:54 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0