题目如下：在一个不重复的1-100的随机数组[1,2,3,7,9,88,94,95,97,99]找出所有和为100的组合，比如[1,99],[2,3,95],[1,2,3,94],[xxx,xx,xx,xxxx]等等。
自己的思路就是简单粗暴遍历，但是效率低，唯一想到的就是排序然后挨个遍历找，直接看下方ChatGPT给出的Java解法代码：
代码语言：javascript复制import java.util.ArrayList;
import java.util.List;
/**
* 在一个不重复的1-100的随机数组[1,2,3,7,9,88,94,95,97,99]找出所有和为100的组合，比如[1,99],[2,3,95],[1,2,3,94],[xxx,xx,xx,xxxx]
*/
public class CombinationSum {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 7, 9, 88, 94, 95, 97, 99};
int target = 100;
List<List<Integer>> combinations = findCombinations(nums, target);
System.out.println(combinations);
}
public static List<List<Integer>> findCombinations(int[] nums, int target) {
List<List<Integer>> combinations = new ArrayList<>();
backtrack(combinations, new ArrayList<>(), nums, target, 0);
return combinations;
}
/**
* 这段代码中，findCombinations方法接收一个整数数组 nums 和目标和 target，并返回一个包含所有和为 target 的组合的列表。
* 我们使用回溯算法进行递归搜索，通过不断选择和取消选择数组中的元素来构建组合。在每一步中，我们检查当前的和是否等于目标和，
* 如果是，则将当前组合添加到结果列表中；如果和小于目标和，则继续向下搜索；如果和大于目标和，则回溯到上一层。
*
* @param combinations 所有组合
* @param currentCombination 当前组合
* @param nums 需要遍历的数组
* @param remaining 需要的求和的值
* @param start 开始索引
*/
private static void backtrack(List<List<Integer>> combinations, List<Integer> currentCombination, int[] nums, int remaining, int start) {
if (remaining == 0) {
combinations.add(new ArrayList<>(currentCombination));
return;
}
if (remaining < 0) {
return;
}
for (int i = start; i < nums.length; i ) {
if (i > start && nums[i] == nums[i - 1]) {
continue; // Skip duplicates
}
currentCombination.add(nums[i]);
backtrack(combinations, currentCombination, nums, remaining - nums[i], i 1);
currentCombination.remove(currentCombination.size() - 1);
}
}
}
