# Problem Definition

## Description

Given a string `s` and a dictionary of words `dict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

```plaintext
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
```

A solution is

```plaintext
[
  "cat sand dog",
  "cats and dog"
]
```

**Make sure the strings are sorted in your result.**

## Notes

1. [ProgramCreek - LeetCode – Word Break II (Java)](https://www.programcreek.com/2014/03/leetcode-word-break-ii-java/)
1. [LeetCode discussion - My concise JAVA solution based on memorized DFS](https://leetcode.com/problems/word-break-ii/discuss/44167/My-concise-JAVA-solution-based-on-memorized-DFS)