面试题：回溯算法递归搜索找到所有组合

题目如下：在一个不重复的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解法代码：

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);
        }
    }
}