[Python3] Simple DFS & Set: 111ms | Beats 91.31%
IntuitionThe key insight is that each word in the list can potentially be formed by concatenating other words from the list. We need to check if we can split a
# Intuition
The key insight is that each word in the list can potentially be formed by concatenating other words from the list. We need to check if we can split a word into multiple valid words that exist in our dictionary. This is a perfect case for using recursion with dynamic programming principles.

# Approach
1. First, convert the list of words into a set for O(1) lookup times
2. Create a helper function `dfs()` that will:
   - Try to split the current word at every possible position
   - Check if the prefix exists in our word set
   - Recursively check if the remaining suffix can be formed from dictionary words
3. For each word:
   - Remove it from the set (to avoid using the word itself)
   - Check if it can be formed by concatenating other words
   - Add it back to the set
4. Use a set to memoize incorrect combinations to avoid redundant work

# Code
```python
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        res = []
        word_set = set(words)
        incorrect = set()

        def dfs(word):
            if word in word_set:
                return True
            elif word in incorrect:
                return False
            else:
                for i in range(1, len(word)):
                    if word[:i] in word_set:
                        if dfs(word[i:]):
                            return True
                        else:
                            incorrect.add(word[i:])
                incorrect.add(word)
                return False
        
        for word in words:
            word_set.remove(word)
            if dfs(word):
                res.append(word)
            word_set.add(word)
        
        return res
```

# Complexity
- Time complexity: $$O(n * 2^m)$$ where n is the number of words and m is the length of the longest word.

- Space complexity: $$O(n)$$ for the word_set and incorrect set, plus $$O(m)$$ for the recursion stack depth.
['Python3']