LeetCode DayBackTracking 第 2 部分

在算法学习中，回溯算法（Backtracking）是一种非常重要且常用的技术，它能够有效解决组合、排列等问题。在LeetCode的刷题过程中，深入理解回溯算法并掌握其应用，对于提升解题能力大有裨益。本文将详细探讨回溯算法的第二部分，在更复杂的场景中如何运用回溯技术。

回溯算法的基本思想

回溯算法的核心思想是“试探性搜索”，它通过递归的方式，逐步尝试不同的选择，并在发现当前选择无效时进行回退。具体而言，回溯算法经历以下几个步骤：

选择

在解决问题时，首先需要做出一个选择，该选择可能是某个数字、字符串或其他形式的元素。在每一步，算法会选择一个可行的选项。

探索

一旦做出选择，算法会进入下一个状态并继续进行选择，这一过程会不断递归下去，直到达到结束条件。

回退

当某条路径无法导致有效的解时，算法会回退到上一步，重新选择不同的选项。这一过程就是“回溯”，它确保了所有可能的选项都被尝试过。

使用回溯算法解决问题

下面将通过几个具体的例子来展示如何运用回溯算法解决问题。

例题：组合总和

题目要求从给定的候选数字中找到所有组合，使得它们的总和等于目标数。题目保证每个数字的使用次数不限。

解决此问题的思路是，选取每个候选数字，递归探索下一个可能的组合。若当前组合的总和超过目标数，则需要进行回退。

import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
    public List> combinationSum(int[] candidates, int target) {
        List> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }
    private void backtrack(List> result, List tempList, int[] candidates, int remain, int start) {
        if (remain < 0) return; // 超过目标，结束当前路径
        if (remain == 0) result.add(new ArrayList<>(tempList)); // 找到有效组合
        
        for (int i = start; i < candidates.length; i++) {
            tempList.add(candidates[i]); // 做出选择
            backtrack(result, tempList, candidates, remain - candidates[i], i); // 递归
            tempList.remove(tempList.size() - 1); // 回退
        }
    }
}

剪枝技术

在回溯算法中，剪枝是一种优化技巧，可以减少不必要的递归调用，从而提高算法效率。通过提前终止某些路径的探索，算法能更快速地找到有效解。

避免重复

在某些问题中，选择相同元素的不同顺序会导致重复解。例如，在处理全排列问题时，可以通过判断当前元素是否已经被使用来避免重复。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Permutations {
    public List> permute(int[] nums) {
        List> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums); // 排序以处理重复元素
        backtrack(result, new ArrayList<>(), nums, used);
        return result;
    }
    private void backtrack(List> result, List tempList, int[] nums, boolean[] used) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList)); // 找到一个排列
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 如果当前数已被使用，跳过
            
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 剪枝
            
            used[i] = true;
            tempList.add(nums[i]); // 做出选择
            backtrack(result, tempList, nums, used); // 递归
            used[i] = false; // 回退
            tempList.remove(tempList.size() - 1);
        }
    }
}

总结与展望

回溯算法是一种强大的解题工具，尤其在组合、排列、子集等问题中展现了其独特优势。掌握回溯算法的基本思路以及剪枝技巧，可以在LeetCode上应对更复杂的问题。下一步，我们可以继续探索更加丰富和多样的回溯算法应用场景，让自己的算法水平不断提升。