LeetCode 1255递归回溯：为何需用.clone()？移除后结果错误

既然已经有第二个for循环用于恢复letterCount数组，为什么还要使用.clone()方法？移除.clone()运行代码会得到错误结果，这个方法的必要性是什么？

相关代码 #

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);
}

解答 #

这俩操作管的是完全不同的递归分支，根本不冲突：

• 后面的for循环是用来恢复当前层里「选择当前单词」操作对原数组的修改。处理完「选单词」的递归分支后，把数组还原成当前层初始状态，避免影响上层递归的逻辑。

• 而.clone()是给**「跳过当前单词」的递归分支**准备的：这个分支需要基于当前层初始的字母计数去递归后续单词。如果直接传原数组引用，「跳过」分支里的递归操作（比如选择后面的单词）会直接修改原数组，等这个分支返回后，原数组已经被改动，再处理「选当前单词」分支时，用的就是被污染的数组状态，必然导致计算错误。

举个实际场景：假设当前层的letterCount是[2, 0, ...]，先调用「跳过」分支，该分支里选择了一个需要第一个字母的单词，把letterCount[0]改成了0。等「跳过」分支返回，原数组的letterCount[0]已经是0了，这时候再处理「选当前单词」（假设当前单词需要第一个字母），会误判为字母不足，直接跳过本应合法的选择，最终结果自然出错。

所以.clone()的核心作用是给「跳过」分支创建独立的数组副本，让它的递归操作完全不干扰原数组，确保两个分支（选/不选当前单词）的状态各自独立，保证整个递归逻辑的正确性。

内容的提问来源于stack exchange，提问作者jonshrey