Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 186
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given an array of positive integers, divide the array into two subsets such that the difference between the sum of the subsets is as small as possible.

For example, given `[5, 10, 15, 20, 25]`, return the sets `{10, 25}` and `{5, 15, 20}`, which has a difference of 5, which is the smallest possible difference.

Pull request description:
Day186
Resolves #382.

Patch:
diff --git a/README.md b/README.md
index b2a2680..8be1705 100644
--- a/README.md
+++ b/README.md
@@ -195,3 +195,4 @@ problems from
 * [Day 182](https://github.com/vaskoz/dailycodingproblem-go/issues/376)
 * [Day 184](https://github.com/vaskoz/dailycodingproblem-go/issues/378)
 * [Day 185](https://github.com/vaskoz/dailycodingproblem-go/issues/381)
+* [Day 186](https://github.com/vaskoz/dailycodingproblem-go/issues/382)
diff --git a/day186/problem.go b/day186/problem.go
new file mode 100644
index 0000000..ff49c14
--- /dev/null
+++ b/day186/problem.go
@@ -0,0 +1,47 @@
+package day186
+
+// SubsetsSmallestDifference returns the two subsets with the
+// smallest difference between them.
+// Brute-force. Runs in O(2^N) time.
+func SubsetsSmallestDifference(nums []int) ([]int, []int) {
+	perms := make(chan [][]int)
+	go func() {
+		permutations(nums, []int{}, []int{}, perms)
+		close(perms)
+	}()
+	minSum := int(^uint(0) >> 1)
+	var s1, s2 []int
+	for subsets := range perms {
+		if s := sum(subsets[0], subsets[1]); s < minSum {
+			minSum = s
+			s1 = subsets[0]
+			s2 = subsets[1]
+		}
+	}
+	return s1, s2
+}
+
+func sum(s1, s2 []int) int {
+	sum := 0
+	for _, v := range s1 {
+		sum += v
+	}
+	for _, v := range s2 {
+		sum -= v
+	}
+	if sum < 0 {
+		return -sum
+	}
+	return sum
+}
+
+func permutations(nums, sub1, sub2 []int, perms chan [][]int) {
+	if len(nums) == 0 {
+		newS1 := append([]int{}, sub1...)
+		newS2 := append([]int{}, sub2...)
+		perms <- [][]int{newS1, newS2}
+		return
+	}
+	permutations(nums[1:], append(sub1, nums[0]), sub2, perms)
+	permutations(nums[1:], sub1, append(sub2, nums[0]), perms)
+}


Test patch:
diff --git a/day186/problem_test.go b/day186/problem_test.go
new file mode 100644
index 0000000..295e10c
--- /dev/null
+++ b/day186/problem_test.go
@@ -0,0 +1,29 @@
+package day186
+
+import (
+	"testing"
+)
+
+var testcases = []struct {
+	nums []int
+	diff int
+}{
+	{[]int{5, 10, 15, 20, 25}, 5},
+}
+
+func TestSubsetsSmallestDifference(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if s1, s2 := SubsetsSmallestDifference(tc.nums); sum(s1, s2) != tc.diff {
+			t.Errorf("Expected a diff of %v, got (%v,%v) for a diff of %v", tc.diff, s1, s2, sum(s1, s2))
+		}
+	}
+}
+
+func BenchmarkSubsetsSmallestDifference(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SubsetsSmallestDifference(tc.nums)
+		}
+	}
+}