Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 42
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null.

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since it sums up to 24.

Pull request:
Day42
Resolves #93 .

Patch:
diff --git a/README.md b/README.md
index f5a3865..bd9f961 100644
--- a/README.md
+++ b/README.md
@@ -53,3 +53,4 @@ problems from
 * [Day 39](https://github.com/vaskoz/dailycodingproblem-go/issues/84)
 * [Day 40](https://github.com/vaskoz/dailycodingproblem-go/issues/87)
 * [Day 41](https://github.com/vaskoz/dailycodingproblem-go/issues/90)
+* [Day 42](https://github.com/vaskoz/dailycodingproblem-go/issues/93)
diff --git a/day42/problem.go b/day42/problem.go
new file mode 100644
index 0000000..f0f5f80
--- /dev/null
+++ b/day42/problem.go
@@ -0,0 +1,43 @@
+package day42
+
+// SubsetSumBrute returns the subset by performing a brute-force search.
+// The first possible result is return if found, otherwise the search is exhaustive.
+// The runtime is exponential.
+func SubsetSumBrute(ints []int, k int) []int {
+	for i, v := range ints {
+		if v == k {
+			return []int{v}
+		} else if k > v {
+			if subset := SubsetSumBrute(ints[i+1:], k-v); len(subset) != 0 {
+				return append([]int{v}, subset...)
+			}
+		}
+	}
+	return nil
+}
+
+// SubsetSumDP returns the subset using dynamic programming.
+// The runtime is O(N*K) with O(N*K) space.
+func SubsetSumDP(ints []int, k int) []int {
+	subsets := make([][][]int, len(ints)+1)
+
+	for i := 0; i <= len(ints); i++ {
+		subsets[i] = make([][]int, k+1)
+		subsets[i][0] = []int{}
+	}
+
+	for i := 1; i <= k; i++ {
+		subsets[0][i] = nil
+	}
+
+	for i := 1; i <= len(ints); i++ {
+		for j := 1; j <= k; j++ {
+			subsets[i][j] = subsets[i-1][j]
+			if j >= ints[i-1] && subsets[i-1][j-ints[i-1]] != nil {
+				subsets[i][j] = append([]int{ints[i-1]}, subsets[i-1][j-ints[i-1]]...)
+			}
+		}
+	}
+
+	return subsets[len(ints)][k]
+}


Test patch:
diff --git a/day42/problem_test.go b/day42/problem_test.go
new file mode 100644
index 0000000..4a7dd2d
--- /dev/null
+++ b/day42/problem_test.go
@@ -0,0 +1,56 @@
+package day42
+
+import (
+	"reflect"
+	"sort"
+	"testing"
+)
+
+var testcases = []struct {
+	input    []int
+	k        int
+	expected []int
+}{
+	{[]int{12, 1, 61, 5, 9, 2}, 24, []int{1, 2, 9, 12}},
+	{[]int{12, 1, 61, 5, 9, 2}, 1000, nil},
+	{[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
+		1000, nil},
+}
+
+func TestSubsetSumBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		result := SubsetSumBrute(tc.input, tc.k)
+		sort.Ints(result)
+		if !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSubsetSumBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SubsetSumBrute(tc.input, tc.k)
+		}
+	}
+}
+
+func TestSubsetSumDP(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		result := SubsetSumDP(tc.input, tc.k)
+		sort.Ints(result)
+		if !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSubsetSumDP(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SubsetSumDP(tc.input, tc.k)
+		}
+	}
+}