【Leetcode】78. 子集

laznrbfe 發(fā)布于2019-08-19 11:15 / 2539人閱讀

摘要：題目給定一組不含重復(fù)元素的整數(shù)數(shù)組，返回該數(shù)組所有可能的子集冪集。說明解集不能包含重復(fù)的子集。示例輸入輸出題解全排列，部分排列這些問題都是回溯的題目。這個(gè)題目每個(gè)狀態(tài)都是解，包括空也是解，所以直接都加進(jìn)去就好。

題目

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復(fù)的子集。

示例:

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

題解

全排列，部分排列這些問題都是回溯的題目。這個(gè)題目每個(gè)狀態(tài)都是解，包括空list也是解，所以直接都加進(jìn)去就好。

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個(gè)排列

【Leetcode】47. 全排列 II

【Leetcode】46.全排列

GPU云服務(wù)器云服務(wù)器子集 a78 php 78E LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/77279.html

相關(guān)文章

【Leetcode】78. 子集

摘要：題目給定一組不含重復(fù)元素的整數(shù)數(shù)組，返回該數(shù)組所有可能的子集冪集。說明解集不能包含重復(fù)的子集。示例輸入輸出題解全排列，部分排列這些問題都是回溯的題目。這個(gè)題目每個(gè)狀態(tài)都是解，包括空也是解，所以直接都加進(jìn)去就好。題目給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。說明：解集不能包含重復(fù)的子集。示例: 輸入: nums = [1,2,3] 輸出: [ ...

miqt 2019-07-30 17:56 評論0 收藏0
「leetcode」78.子集

摘要：原題給定一組不含重復(fù)元素的整數(shù)數(shù)組，返回該數(shù)組所有可能的子集冪集。說明解集不能包含重復(fù)的子集。示例輸入輸出思路使用位移和按位與的思路，來自的評論區(qū)。這個(gè)思路相對來說比較抽象，下面是具體的解釋。 showImg(https://segmentfault.com/img/remote/1460000020181883); 原題給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的...

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

摘要：題目地址題目描述給定一組不含重復(fù)元素的整數(shù)數(shù)組，返回該數(shù)組所有可能的子集冪集。說明解集不能包含重復(fù)的子集。示例輸入輸出解答這一題用回溯法。對于長度為的數(shù)組，它的解空間應(yīng)該是這樣的這里的或者，代表第個(gè)數(shù)放或者不放入子集。題目地址：https://leetcode-cn.com/probl...題目描述：給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。說明：...

rollback 2019-08-16 15:17 評論0 收藏0
LeetCode 子集合，排列組合，回文分離等問題的通用遞歸算法

摘要：通用算法思路總結(jié)初始結(jié)果列表。可能要將數(shù)集排序，方便處理重復(fù)元素的情況。書寫遞歸函數(shù)，先要考慮原點(diǎn)狀況，一般就是考慮什么情況下要將當(dāng)前結(jié)果添加到結(jié)果列表中。每當(dāng)一個(gè)元素添加到當(dāng)前結(jié)果中之后，要再調(diào)用遞歸函數(shù)，相當(dāng)于固定了前綴窮舉后面的變化。通用算法思路總結(jié)：初始結(jié)果列表。可能要將數(shù)集排序，方便處理重復(fù)元素的情況。調(diào)用遞歸函數(shù)。書寫遞歸函數(shù)，先要考慮原點(diǎn)狀況，一般就是考慮什么...

cfanr 2019-08-14 15:54 評論0 收藏0
6-9月技術(shù)文章匯總

摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0