-
Notifications
You must be signed in to change notification settings - Fork 1
/
set.go
52 lines (48 loc) · 1.09 KB
/
set.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package set
func subSets(nums []int) [][]int {
n := len(nums)
total := 1 << n
ret := make([][]int, 0, total)
backtrack(&ret, []int{}, nums, 0)
return ret
}
// backtrack time complexity # of nodes O(2^N), space complexity O(N)
func backtrack(ret *[][]int, store, nums []int, pos int) {
*ret = append((*ret), store)
for i := pos; i < len(nums); i++ {
ns := len(store)
store = append(store, nums[i])
backtrack(ret, store, nums, i+1)
store = store[:ns]
}
}
func helper(res *[][]int, nums, temp []int, start, target int) {
if len(temp) == target {
bak := make([]int, target)
copy(bak, temp)
*res = append(*res, bak)
} else {
for i := start; i < len(nums); i++ {
n := len(temp)
temp = append(temp, nums[i])
helper(res, nums, temp, i+1, target)
temp = temp[:n]
}
}
}
func SubSets2(nums []int) [][]int {
// bit manupulation
n := len(nums)
total := 1 << uint(n)
ret := make([][]int, 0, total)
for i := 0; i < total; i++ {
var cur []int
for j := 0; j < n; j++ {
if (i>>uint(j))&1 != 0 {
cur = append(cur, nums[j])
}
}
ret = append(ret, cur)
}
return ret
}