LC39. 组合总和

题目描述

给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。所有组合（包括解集）不能包含重复组合。

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释：2+2+3=7，7=7。

思路解析

核心思路：回溯法（深度优先搜索）。 1. 排序（可选）：先对 candidates 排序，有助于剪枝。 2. 回溯函数：参数包括当前起始索引（避免重复组合）、当前路径、当前和。 3. 剪枝：如果当前和大于 target，直接返回；如果等于 target，将路径加入结果。 4. 递归：从当前索引开始遍历，因为数字可重复使用，所以递归时起始索引不变。