Untitled

import java.util.*;

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);  // Fast lookup
        List<String> results = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        backtrack(s, wordSet, 0, current, results);
        return results;
    }

    private void backtrack(String s, Set<String> wordSet, int start, StringBuilder current, List<String> results) {
        // If we've reached the end, add the current sentence (trim extra space) to results.
        if (start == s.length()) {
            results.add(current.toString().trim());
            return;
        }
        
        int originalLength = current.length();
        
        // Try every possible split starting from 'start'
        for (int i = start + 1; i <= s.length(); i++) {
            String word = s.substring(start, i);
            if (wordSet.contains(word)) {
                // Append a space only if current is not empty.
                if (current.length() != 0) {
                    current.append(" ");
                }
                current.append(word);
                
                // Recurse for the remaining substring.
                backtrack(s, wordSet, i, current, results);
                
                // Backtrack: remove the appended word (and space if it was added).
                current.setLength(originalLength);
            }
        }
    }
}