How Would I refactor this Depth First Search function to remove mutation

Question

So I'm currently working my way through an algorithms course and this was provided as the answer for the leetcode problem "Palindrome Partitioning". I would like to be able to refactor the code so that it does not mutate the answer array and instead returns it. Preferably there would be no separate dfs function, just one recursive function called partition. I'm normally decent at this kind of thing but I'm struggling with this one:

function partition(s) {
    const ans = [];
    const n = s.length;
    function dfs(start, part) {
        if (start == n) {
            ans.push([...part]);
            return;
        }
        for (let i = start + 1; i < n + 1; i++) {
            const prefix = s.substring(start, i);
            if (isPalindrome(prefix)) {
                part.push(prefix);
                dfs(i, part);
                part.pop();
            }
        }
    }
    dfs(0, []);
    return ans;
}

This is my attempt so far:

function partition(str, start) {
    const result = [];
    
    if (start == str.length) {
        result.push([str]);
    } else {
        for (let i = start + 1; i < str.length; i++) {
            const prefix = s.substring(start, i);

            if (isPalindrome(prefix)) {
                const results = partition(str, start + 1);
                
                if (results.length) {
                    for (const r of results) {
                        result.push([prefix, ...r]);
                    }
                } else {
                    result.push([prefix, s.substring(i + 1)]);
                }              
            }
        }
    }
    
    return result;
}

Answer 1

Your attempt needs a few corrections:

• Spelling of s and str is not consistent
• The start parameter needs a default value of 0
• The recursive call is made with a wrong index. Not start + 1, but i
• The base case should not place the whole string in an array. On the contrary that newly pushed array should be empty: result.push([]) or why not return [[]] immediately.
• results.length will never be zero when coming back from recursion; the else block will never execute -- it can be omitted.
• The for loop is making one iteration too few. The end condition should be i <= s.length

Here is the corrected version:

function partition(s, start=0) {
    if (start == s.length) {
        return [[]];
    }
    let result = [];
    for (let i = start + 1; i <= s.length; i++) {
        const prefix = s.slice(start, i);
        if (isPalindrome(prefix)) {
            for (const part of partition(s, i)) {
                result.push([prefix, ...part]);
            }
        }
    }
    return result;
}

Note that this makes the solution a tad slower.