Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 37
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

The power set of a set is the set of all its subsets. Write a function that, given a set, generates its power set.

For example, given the set {1, 2, 3}, it should return {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

You may also use a list or array to represent a set.

Pull request:
Day37
Resolves #81 .

Patch:
diff --git a/README.md b/README.md
index f9dafaf..88f6aff 100644
--- a/README.md
+++ b/README.md
@@ -48,3 +48,4 @@ problems from
 * [Day 33](https://github.com/vaskoz/dailycodingproblem-go/issues/73)
 * [Day 35](https://github.com/vaskoz/dailycodingproblem-go/issues/77)
 * [Day 36](https://github.com/vaskoz/dailycodingproblem-go/issues/79)
+* [Day 37](https://github.com/vaskoz/dailycodingproblem-go/issues/81)
diff --git a/day37/problem.go b/day37/problem.go
new file mode 100644
index 0000000..6ab7096
--- /dev/null
+++ b/day37/problem.go
@@ -0,0 +1,18 @@
+package day37
+
+import "math/bits"
+
+// PowerSet returns all subsets.
+func PowerSet(set []int) [][]int {
+	result := make([][]int, 0, 1<<uint64(len(set)))
+	for i := uint64(0); i < (1 << uint64(len(set))); i++ {
+		entry := make([]int, 0, bits.OnesCount64(i))
+		for pos := 0; pos < len(set); pos++ {
+			if i&(1<<uint64(pos)) != 0 {
+				entry = append(entry, set[pos])
+			}
+		}
+		result = append(result, entry)
+	}
+	return result
+}


Test patch:
diff --git a/day37/problem_test.go b/day37/problem_test.go
new file mode 100644
index 0000000..4ef8997
--- /dev/null
+++ b/day37/problem_test.go
@@ -0,0 +1,39 @@
+package day37
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	input    []int
+	expected [][]int
+}{
+	{[]int{1, 2, 3}, [][]int{{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}},
+	{[]int{4, 2, 3, 6}, [][]int{{}, {4}, {2}, {4, 2}, {3}, {4, 3}, {2, 3},
+		{4, 2, 3}, {6}, {4, 6}, {2, 6}, {4, 2, 6}, {3, 6}, {4, 3, 6}, {2, 3, 6}, {4, 2, 3, 6}}},
+}
+
+func TestPowerSet(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		result := PowerSet(tc.input)
+		if len(result) != len(tc.expected) {
+			t.Errorf("Length of result doesn't match. Expected %v got %v", len(tc.expected), len(result))
+			continue
+		}
+		for i := range result {
+			if !reflect.DeepEqual(result[i], tc.expected[i]) {
+				t.Errorf("Expected %v got %v", tc.expected[i], result[i])
+			}
+		}
+	}
+}
+
+func BenchmarkPowerSet(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PowerSet(tc.input)
+		}
+	}
+}