回溯算法java

回溯算法是一种基于深度优先搜索的算法，常用于解决组合问题、排列问题和选择问题等。在Java中，可以通过递归实现回溯算法。

下面是一个求解组合问题的Java代码示例，假设有一个数组`nums`和一个整数`k`，需要从数组中选出k个数的所有组合。

import java.util.ArrayList;
import java.util.List;

public class Combination {
    public List<List<Integer>> combine(int[] nums, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(nums, k, 0, path, res);
        return res;
    }

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

在这个代码中，`dfs()`方法是递归的核心方法，其中`nums`是原始数组，`k`是需要选取的元素个数，`start`表示从哪个位置开始选取元素，`path`是当前已选取的元素列表，`res`是最终的结果列表。

在`dfs()`方法中，首先判断当前已经选取的元素个数是否达到了要求，如果达到了，就将当前的元素列表加入到结果列表中。否则，从`start`位置开始遍历原始数组，将当前元素加入到已选取元素列表中，并递归调用`dfs()`方法选取下一个元素，最后将已选取元素列表中的当前元素移除，继续尝试其他元素的选取。

通过这种方式，可以遍历出所有可能的组合，并将它们保存在结果列表中。