图片发到哪些网站 seo,直播软件排行榜2020,抛丸机网站排名优化,app开发网站建设哪家好一、题目概述 二、思路方向 为了解决这个问题#xff0c;我们可以使用回溯算法来找到所有可能的组合#xff0c;使得组合中的数字之和等于目标数 target。因为数组中的元素可以无限制地重复选择#xff0c;所以在回溯过程中#xff0c;我们不需要跳过已经选择的元素#x…一、题目概述 二、思路方向 为了解决这个问题我们可以使用回溯算法来找到所有可能的组合使得组合中的数字之和等于目标数 target。因为数组中的元素可以无限制地重复选择所以在回溯过程中我们不需要跳过已经选择的元素而是可以从当前位置开始继续选择。 三、代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class Solution { ListListInteger result new ArrayList(); public ListListInteger combinationSum(int[] candidates, int target) { Arrays.sort(candidates); // 对数组进行排序有助于提前结束回溯 ListInteger tempList new ArrayList(); backtrack(candidates, target, 0, tempList); return result; } private void backtrack(int[] candidates, int remain, int start, ListInteger tempList) { if (remain 0) { return; // 如果剩余需要达到的和已经是负数则剪枝 } if (remain 0) { result.add(new ArrayList(tempList)); // 如果剩余需要达到的和为0则找到了一种符合条件的组合 return; } for (int i start; i candidates.length; i) { // 因为元素可以重复选择所以我们不需要跳过已经选择过的元素 // 但可以通过排序和剪枝来避免不必要的搜索 if (i start candidates[i] candidates[i - 1]) { continue; // 跳过重复的元素避免产生重复的组合 } tempList.add(candidates[i]); backtrack(candidates, remain - candidates[i], i, tempList); // 注意这里是从i开始允许选择相同的数字 tempList.remove(tempList.size() - 1); // 回溯撤销选择 } } public static void main(String[] args) { Solution solution new Solution(); int[] candidates {2, 3, 6, 7}; int target 7; ListListInteger combinations solution.combinationSum(candidates, target); for (ListInteger combination : combinations) { System.out.println(combination); } }
}
执行结果 四、小结 在这个解决方案中我们首先对数组进行排序这是为了在处理过程中能够更方便地进行剪枝和跳过重复元素。然后我们使用一个递归函数 backtrack 来遍历所有可能的组合。在递归函数中我们检查当前的和是否等于目标值或者是否已经是负数如果是负数则剪枝。然后我们遍历数组从当前位置开始选择元素并递归地调用 backtrack 函数传入剩余需要达到的和、下一个开始的位置允许选择相同的数字、以及当前的组合列表。最后在回溯过程中我们需要撤销选择以便尝试其他可能的组合。 注意在这个解决方案中我们使用了 ListListInteger 来存储所有可能的组合并且使用 ArrayList 作为内部的临时列表来构建每个组合。在找到一种符合条件的组合时我们通过创建一个新的 ArrayList 实例来将其添加到结果列表中以避免在后续的回溯过程中修改已经添加到结果列表中的组合。 结语 只有流过血的手指 才能弹出世间的绝唱
