Skip to content

Instantly share code, notes, and snippets.

@lzambarda
Last active April 20, 2022 11:56
Show Gist options
  • Save lzambarda/141d2629ca58b4d2ce53c107567c3ab2 to your computer and use it in GitHub Desktop.
Save lzambarda/141d2629ca58b4d2ce53c107567c3ab2 to your computer and use it in GitHub Desktop.
Find powerset in go
// https://play.golang.com/p/nVrmIlgzZac
package main
import (
"fmt"
)
// FindPowerSet does not include the empty set.
// The imput set must already be distinct values.
func FindPowerSet(set []string) (powerset [][]string) {
l := len(set)
if l == 0 {
return nil
}
// Check all combinations
for i := 1; i < 2<<(l-1); i++ {
subset := []string{}
// Consider each element in the set
for j := 0; j < l; j++ {
// Check if jth bit in the i is set. If the bit is set, we consider
// jth element from set.
if (i & (1 << j)) != 0 {
subset = append(subset, set[j])
}
}
powerset = append(powerset, subset)
}
return powerset
}
func main() {
fmt.Println(FindPowerSet([]string{"A", "B", "C"}))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment