力扣 回溯算法 java

力扣是一个在线编程平台，提供了大量的算法题目，可以帮助程序员提高算法能力。回溯算法是一种搜索算法，它通过不断地尝试所有可能的解来求解问题。在回溯算法中，我们首先定义一个解空间，然后从解空间中搜索所有可能的解，直到找到符合要求的解为止。回溯算法通常用于求解组合问题、排列问题、子集问题等。

在 Java 中实现回溯算法，通常需要定义一个递归函数来搜索解空间。在递归函数中，我们首先判断当前状态是否符合要求，如果符合要求，则将当前状态加入到解集中；否则，我们继续搜索下一个状态。在搜索下一个状态时，我们需要对当前状态进行一些修改，然后递归调用自身来搜索下一个状态。当搜索完所有可能的状态后，我们需要回溯到上一个状态，继续搜索其他可能的状态。

以下是回溯算法的一般步骤：

1. 定义解空间：确定问题的解空间，并定义一个数据结构来表示解空间中的每个状态。
2. 确定约束条件：确定哪些状态是合法的，并定义一个函数来判断当前状态是否符合要求。
3. 确定搜索策略：确定搜索解空间的顺序，并定义一个函数来生成下一个状态。
4. 搜索解空间：使用递归函数搜索解空间，如果当前状态符合要求，则将其加入到解集中；否则，继续搜索下一个状态。
5. 回溯：当搜索完所有可能的状态后，回溯到上一个状态，继续搜索其他可能的状态。

以下是一个力扣题目的回溯算法 Java 实现示例：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int start) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

该算法用于求解给定数组的所有子集。在递归函数中，我们首先将当前状态加入到解集中，然后从当前位置开始搜索下一个状态。在搜索下一个状态时，我们将当前元素加入到路径中，并递归调用自身来搜索下一个状态。当搜索完所有可能的状态后，我们需要回溯到上一个状态，继续搜索其他可能的状态。