组合（力扣）dfs + 回溯 + 剪枝 JAVA

**组合问题**

组合问题是指从一个集合中选取若干个元素，形成新的集合，而这些元素可以重复选择。例如，从1 到9 的数字中选取3 个数字，形成一个三位数。

在力扣的组合问题中，我们需要使用 DFS（深度优先搜索）和回溯法来解决这个问题。我们还会使用剪枝技术来减少计算量。

**DFS + 回溯**

首先，让我们了解一下 DFS 和回溯法的基本概念：

* DFS：从一个起始点出发，沿着某一条路径向前探索，直到达到终止条件或找到所需结果。
* 回溯法：在 DFS 中，当遇到无法继续向前的情况时，退回到上一步，并尝试其他可能的路径。

**剪枝技术**

剪枝技术是指在 DFS 过程中，根据某些条件判断当前路径是否有必要继续探索。例如，如果当前数字已经大于目标数字，则可以立即返回，不需要继续探索。

**JAVA代码示例**

javapublic class Combination {
 public List> combinationSum(int[] candidates, int target) {
 // 初始化结果列表 List> result = new ArrayList<>();

 // 使用 DFS 和回溯法进行组合计算 dfs(result, new ArrayList<>(), candidates, target,0);

 return result;
 }

 private void dfs(List> result, List tempList, int[] nums, int remain, int start) {
 // 如果剩余值为零，则表示找到了一种有效组合，添加到结果列表中 if (remain ==0) {
 result.add(new ArrayList<>(tempList));
 return;
 }

 // 遍历候选数字数组 for (int i = start; i < nums.length; i++) {
 // 如果当前数字大于剩余值，则可以立即返回，不需要继续探索 if (nums[i] > remain) {
 break;
 }

 // 将当前数字添加到临时列表中 tempList.add(nums[i]);

 // 递归调用 DFS，继续探索下一个数字 dfs(result, tempList, nums, remain - nums[i], i);

 // 回溯法：从临时列表中移除当前数字，准备探索其他可能的路径 tempList.remove(tempList.size() -1);
 }
 }

 public static void main(String[] args) {
 Combination combination = new Combination();
 int[] candidates = {2,3,6,7};
 int target =7;
 List> result = combination.combinationSum(candidates, target);

 System.out.println("组合结果:");
 for (List list : result) {
 System.out.println(list);
 }
 }
}