0078. Subsets

題目

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2:

Input: nums = [0] Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10 All the numbers of nums are unique.

題目大意

給定一組不含重複元素的整數陣列 nums，返回該陣列所有可能的子集（冪集）。 說明：解集不能包含重複的子集。

解題思路

找出一個集合中的所有子集，空集也算是子集。 且陣列中的數位不會出現重複。 用 DFS 暴力枚舉即可。 這一題和第 90 題，第 491 題類似，可以一起解答和複習

Big O

時間複雜 : O(n^2) 空間複雜 : O(n)

來源

• https://leetcode.com/problems/subsets/description/
• https://leetcode.cn/problems/subsets/description/
• https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0078.Subsets/
• https://github.com/suntong/lang/blob/master/lang/Go/src/ds/Recursion/LC-0B-Subsets-2.go

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0078.Subsets/main.go

package subsets

// 時間複雜 O(n^2)    , 空間複雜 O(n)
func Subsets(nums []int) [][]int {
    path, result := []int{}, [][]int{}
    for i := 0; i 

Benchmark

go test -benchmem -run=none LeetcodeGolang/Leetcode/0354.Russian-Doll-Envelopes -bench=. -cover
goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0354.Russian-Doll-Envelopes
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
BenchmarkMaxEnvelopes-8          7799131               160.3 ns/op            88 B/op          3 allocs/op
BenchmarkMaxEnvelopes2-8         5800399               195.6 ns/op            80 B/op          4 allocs/op
PASS
coverage: 96.0% of statements
ok      LeetcodeGolang/Leetcode/0354.Russian-Doll-Envelopes     3.726s