Skip to main content

78. Subsets

分析

1. 选 / 不选

注意选的时候回退选择

2. 选第几个

题解

选或者不选,在叶子结点进行操作

func subsets(nums []int) [][]int {
n := len(nums)
ans := [][]int{}
temp := []int{}

var dfs func(int)
dfs = func (index int) {
if index == n {
copyFromTemp := make([]int, len(temp))
copy(copyFromTemp, temp)
ans = append(ans, copyFromTemp)
return
}
// not choose
dfs(index + 1)
// choose
temp = append(temp, nums[index])
dfs(index + 1)
temp = temp[:len(temp) - 1]
}

dfs(0)

return ans
}

选第几个, 进入的时候就进行添加操作

func subsets(nums []int) [][]int {
n := len(nums)
ans := [][]int{}
temp := []int{}

var dfs func(int)
dfs = func(start int) {
copyFromTemp := make([]int, len(temp))
copy(copyFromTemp, temp)
ans = append(ans, copyFromTemp)
for i := start; i < n; i++ {
temp = append(temp, nums[i])
dfs(i + 1)
temp = temp[:len(temp)-1]
}

}

dfs(0)

return ans
}