Word Break Combinations

Implement a function that determines all possible ways to split a given string into valid words based on a provided dictionary. Use backtracking to explore all combinations. Input format: - The first line contains a string s (1 <= len(s) <= 20), the input string. - The second line contains an integer N (1 <= N <= 10), the number of words in the dictionary. - The next N lines contain words of the dictionary. Output format: - Print all possible sentences formed by valid words in the dictionary. Example: Input: applepie 3 apple pie ap Output: [['apple', 'pie'], ['ap', 'ple', 'pie']]