《零基础Go语言算法实战》【题目 4-12】找到给定集合的所有子集
《零基础Go语言算法实战》
【题目 4-12】找到给定集合的所有子集
如何在 Go 语言中实现通过穷举搜索找到给定集合的所有子集？
【解答】
package main
import "fmt"
func subsets(set []int) [][]int {
n := len(set)
power := 1 << uint(n)
subsets := make([][]int, 0)
for i := 0; i < power; i++ {
subset := make([]int, 0)
for j := 0; j < n; j++ {
if i&(1<<uint(j)) != 0 {
subset = append(subset, set[j])
}
}
subsets = append(subsets, subset)
}
return subsets
}
func main() {
set := []int{1, 6, 8}
result := subsets(set)
fmt.Println(result)
}
//$ go run interview4-12.go
//[[] [1] [6] [1 6] [8] [1 8] [6 8] [1 6 8]]
在以上代码中，subsets() 函数将一组整数作为输入并返回所有可能子集的一部分。它使
用一种位操作技术来生成所有可能的子集，其中数字的二进制表示中的每一位表示集合中的
相应元素是否应包含在子集中。该函数迭代所有可能的数字，直到 2的n次方，其中 n 是集合的长度。
对于每个数字，它检查哪些位设置为 1，并将相应的元素添加到子集中。