Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 379
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given a string, generate all possible subsequences of the string.

For example, given the string `xyz`, return an array or set with the following strings:

```
x
y
z
xy
xz
yz
xyz
```
Note that `zx` is not a valid subsequence since it is not in the order of the given string.

Pull request description:
Day379
Resolves #764.

Patch:
diff --git a/README.md b/README.md
index d7d471a..e3d0159 100644
--- a/README.md
+++ b/README.md
@@ -374,4 +374,5 @@ problems from
 * [Day 376](https://github.com/vaskoz/dailycodingproblem-go/issues/758)
 * [Day 377](https://github.com/vaskoz/dailycodingproblem-go/issues/760)
 * [Day 378](https://github.com/vaskoz/dailycodingproblem-go/issues/762)
+* [Day 379](https://github.com/vaskoz/dailycodingproblem-go/issues/764)
 
diff --git a/day379/problem.go b/day379/problem.go
new file mode 100644
index 0000000..2b9685d
--- /dev/null
+++ b/day379/problem.go
@@ -0,0 +1,23 @@
+package day379
+
+// AllPossibleSubsequences returns all the possible
+// ordered subsequences.
+func AllPossibleSubsequences(str string) map[string]struct{} {
+	ansSet := make(map[string]struct{})
+	allPossibleSubsequences(str, ansSet)
+
+	return ansSet
+}
+
+func allPossibleSubsequences(str string, ansSet map[string]struct{}) {
+	if _, alreadyExists := ansSet[str]; len(str) == 0 || alreadyExists {
+		return
+	}
+
+	for i := range str {
+		sub := str[:i] + str[i+1:]
+		allPossibleSubsequences(sub, ansSet)
+	}
+
+	ansSet[str] = struct{}{}
+}


Test patch:
diff --git a/day379/problem_test.go b/day379/problem_test.go
new file mode 100644
index 0000000..20658c6
--- /dev/null
+++ b/day379/problem_test.go
@@ -0,0 +1,41 @@
+package day379
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input  string
+	subseq map[string]struct{}
+}{
+	{"xyz",
+		map[string]struct{}{
+			"x":   {},
+			"y":   {},
+			"z":   {},
+			"xy":  {},
+			"xz":  {},
+			"yz":  {},
+			"xyz": {},
+		}},
+}
+
+func TestAllPossibleSubsequences(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := AllPossibleSubsequences(tc.input); !reflect.DeepEqual(result, tc.subseq) {
+			t.Errorf("Expected %v, got %v", tc.subseq, result)
+		}
+	}
+}
+
+func BenchmarkAllPossibleSubsequences(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			AllPossibleSubsequences(tc.input)
+		}
+	}
+}