[LeetCode]Combination Sum

题目传送门

题目描述：给定一个没有重复元素的整数数组 candidates 和一个目标值 target，要求找出所有可以使数字和等于 target 的组合；其中每个数字可以被无限次重复使用，但每种组合中数字的顺序不重要，因此像 [2,3] 和 [3,2] 视为同一个组合，结果中不能包含重复解，最终返回所有满足条件的组合列表。

代码：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        combinationSum(result, candidates, target, new ArrayList<>(), 0, 0);
        return result;
    }

    private void combinationSum(List<List<Integer>> result, int[] candidates, int target, List<Integer> lastArray,
                                int lastSum, int lastIndex) {
        if (lastSum == target) {
            result.add(new ArrayList<>(lastArray));
            return;
        }
        for (int i = lastIndex; i < candidates.length; i++) {
            int sum = lastSum + candidates[i];
            if (sum <= target) {
                lastArray.add(candidates[i]);
                combinationSum(result, candidates, target, lastArray, sum, i);
                lastArray.removeLast();
            }
        }
    }
}

代码思路：通过递归不断构建当前组合 lastArray，并用 lastSum 记录当前和，当和等于 target 时将该组合加入结果；在每一层递归中，从 lastIndex 开始遍历数组，选择一个数加入组合并继续递归（传入当前索引以实现元素可重复使用），若当前和超过 target 则停止该路径（剪枝）；递归返回后再移除刚加入的元素进行回溯，从而尝试其他可能，同时通过 lastIndex 控制搜索顺序，避免生成重复组合，最终得到所有满足条件的结果。