Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 60
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a multiset of integers, return whether it can be partitioned into two subsets whose sums are the same.

For example, given the multiset {15, 5, 20, 10, 35, 15, 10}, it would return true, since we can split it up into {15, 5, 10, 15, 10} and {20, 35}, which both add up to 55.

Given the multiset {15, 5, 20, 10, 35}, it would return false, since we can't split it up into two subsets that add up to the same sum.

Pull request:
Day60
Resolves #130.

Patch:
diff --git a/README.md b/README.md
index 54fbb31..f0cc99f 100644
--- a/README.md
+++ b/README.md
@@ -70,3 +70,4 @@ problems from
 * [Day 56](https://github.com/vaskoz/dailycodingproblem-go/issues/123)
 * [Day 57](https://github.com/vaskoz/dailycodingproblem-go/issues/124)
 * [Day 58](https://github.com/vaskoz/dailycodingproblem-go/issues/127)
+* [Day 60](https://github.com/vaskoz/dailycodingproblem-go/issues/130)
diff --git a/day60/problem.go b/day60/problem.go
new file mode 100644
index 0000000..674eaaa
--- /dev/null
+++ b/day60/problem.go
@@ -0,0 +1,55 @@
+package day60
+
+// BruteForcePartitionSet returns if partitioning into 2-sets with equal sums is possible.
+// Runs in O(2^N) time.
+func BruteForcePartitionSet(multiset []int) bool {
+	sum := 0
+	for _, num := range multiset {
+		sum += num
+	}
+	if sum%2 == 1 {
+		return false
+	}
+	half := sum / 2
+	return subsetSum(multiset, half)
+}
+
+func subsetSum(multiset []int, target int) bool {
+	for i, v := range multiset {
+		if remainder := target - v; remainder > 0 {
+			if subsetSum(multiset[i+1:], remainder) {
+				return true
+			}
+		} else if remainder == 0 {
+			return true
+		}
+	}
+	return false
+}
+
+// PartitionSet returns if partitioning into 2-sets with equal sums is possible.
+// Runs in O(K*N) time using O(K*N) additional space.
+// K is the sum of the elements in the input and N is the size of the input.
+func PartitionSet(multiset []int) bool {
+	sum := 0
+	for _, num := range multiset {
+		sum += num
+	}
+	p := make([][]bool, (sum/2)+1)
+	for i := range p {
+		p[i] = make([]bool, len(multiset)+1)
+	}
+	for i := 0; i < len(multiset)+1; i++ {
+		p[0][i] = true
+	}
+	for i := 1; i <= sum/2; i++ {
+		for j := 1; j <= len(multiset); j++ {
+			if i-multiset[j-1] >= 0 {
+				p[i][j] = p[i][j-1] || p[i-multiset[j-1]][j-1]
+			} else {
+				p[i][j] = p[i][j-1]
+			}
+		}
+	}
+	return p[sum/2][len(multiset)]
+}


Test patch:
diff --git a/day60/problem_test.go b/day60/problem_test.go
new file mode 100644
index 0000000..8286574
--- /dev/null
+++ b/day60/problem_test.go
@@ -0,0 +1,53 @@
+package day60
+
+import "testing"
+
+var testcases = []struct {
+	multiset []int
+	expected bool
+}{
+	{[]int{15, 5, 20, 10, 35, 15, 10}, true},
+	{[]int{15, 5, 20, 10, 35}, false},
+	{[]int{5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2,
+		5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5,
+		2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2,
+		5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2}, true},
+	{[]int{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, true},
+}
+
+func TestBruteForcePartitionSet(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := BruteForcePartitionSet(tc.multiset); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkBruteForcePartitionSet(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BruteForcePartitionSet(tc.multiset)
+		}
+	}
+}
+
+func TestPartitionSet(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PartitionSet(tc.multiset); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkPartitionSet(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PartitionSet(tc.multiset)
+		}
+	}
+}