如何在 Go 语言中生成所有子集组合（幂集）-Golang-PHP中文网

如何在 Go 语言中生成所有子集组合（幂集）

本文介绍使用迭代法在 go 中高效生成字符串切片的全部非空子集组合（即幂集），涵盖核心算法原理、完整可运行代码、边界处理及性能提示。

本文介绍使用迭代法在 go 中高效生成字符串切片的全部非空子集组合（即幂集），涵盖核心算法原理、完整可运行代码、边界处理及性能提示。

在 Go 中生成一个字符串切片的所有组合（即幂集，Power Set），本质是枚举所有可能的子集——包括空集，但通常业务场景中我们只需非空子集，并按字符串拼接形式（如 "ab"、"bcd"）输出。关键在于避免递归带来的栈开销与复杂度，采用迭代构建法：从空集开始，逐个加入元素，并将该元素追加到已有所有子集中，从而指数级扩展结果。

以下是简洁、健壮、符合 Go 风格的实现：

package main

import "fmt"

// PowerSet returns all non-empty subsets of input as joined strings
func PowerSet(letters []string) []string {
    if len(letters) == 0 {
        return nil
    }

    // Start with empty subset represented as empty slice
    result := [][]string{{}} // contains one empty slice: [[]]

    // Iteratively add each letter
    for _, letter := range letters {
        // Snapshot current result before modification
        current := make([][]string, len(result))
        for i, v := range result {
            current[i] = append([]string(nil), v...) // deep copy
        }

        // For each existing subset, append current letter → new subset
        for _, subset := range current {
            newSubset := append(subset, letter)
            result = append(result, newSubset)
        }
    }

    // Convert [][]string to []string, skip empty subset
    var output []string
    for _, subset := range result[1:] { // skip index 0 (the empty subset)
        output = append(output, joinStrings(subset))
    }
    return output
}

// joinStrings concatenates string slice into single string (e.g. ["a","b"] → "ab")
func joinStrings(ss []string) string {
    if len(ss) == 0 {
        return ""
    }
    res := ""
    for _, s := range ss {
        res += s
    }
    return res
}

func main() {
    letters := []string{"a", "b", "c", "d"}
    combinations := PowerSet(letters)
    fmt.Println(combinations)
    // Output (order matches iterative growth):
    // [a b ab c ac bc abc d ad bd abd cd acd bcd abcd]
}

✅ 关键说明：