131. Palindrome Partitioning

class Solution {

    public List<List<String>> partition(String s) 
    {

        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for(int i = 0; i < n; i++) 
        {
            dp[i][i] = true;
        }

        for (int length = 2; length <= n; length++) 
        {
            for (int i = 0; i <= n - length; i++) 
            {
                int j = i + length - 1;

                if (s.charAt(i) == s.charAt(j) && (length == 2 || dp[i + 1][j - 1])) 
                {
                    dp[i][j] = true;
                }
            }
        }

        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result, dp);
        return result;

    }

    public void backtrack(String s, int start, List<String> path, List<List<String>> result, boolean[][] dp) 
    {

        if (start == s.length())
        {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int end = start; end < s.length(); end++) 
        {

            if (dp[start][end]) 
            {
                path.add(s.substring(start, end + 1));
                
                backtrack(s, end + 1, path, result, dp);

                path.remove(path.size() - 1);
            }
        }
    }





}