javarecursiondynamic-programmingclonebacktracking

Leetcode 1255-recursion and backtracking


I dont quite understand why have we used .clone() method when we have a second for loop to restore the letterCount.And when i'm runnig this code without .clone() method its giving me the wrong answer? So what exactly is the need

public int solution(String[] words, int[] letterCount, int[] score, int ind) {
    if (ind == words.length)
        return 0;

    int sno = solution(words, letterCount.clone(), score, ind + 1); // Skip word

    String word = words[ind];
    int sword = 0;
    boolean flag = true;

    for (char ch : word.toCharArray()) {
        int letterIndex = ch - 'a';
        if (letterCount[letterIndex] == 0) {
            flag = false;
            break;
        }
        letterCount[letterIndex]--;
        sword += score[letterIndex];
    }

    int syes = 0;
    if (flag) 
        syes = sword + solution(words, letterCount, score, ind + 1); // Use word

    // Restore letterCount 
    for (char ch : word.toCharArray()) {
        letterCount[ch - 'a']++;
    }
    return Math.max(sno, syes);
}

Solution

  • Your backtracking doesn't work, as you break when the count of a letter drops to 0, but the loop that restores the counts unconditionally adds all the letters back.

    If you remove the break, then your code will work correctly without cloning.

    for (char ch : word.toCharArray()) {
        int letterIndex = ch - 'a';
        if (letterCount[letterIndex] == 0)
            flag = false;
        letterCount[letterIndex]--;
        sword += score[letterIndex];
    }