哪吒的“乾坤圈”与递归：如何用代码找到所有组合？
大家好，我是哪吒，今天不闹海，也不打龙王，咱们来聊聊递归和组合问题。你可能会问，哪吒你一个神仙，怎么还搞起代码来了？嘿，这不都是为了给你们这些凡人传授点“仙法”嘛！
问题描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为 target 的所有不同组合。你可以按任意顺序返回这些组合。
注意：candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
示例
示例 1：
- 输入：candidates = [2,3,6,7], target = 7
- 输出：[[2,2,3],[7]]
- 解释：
- 2 和 3 可以形成一组候选，2 + 2 + 3 = 7。注意 2 可以使用多次。
- 7 也是一个候选，7 = 7。
- 仅有这两种组合。
示例 2：
- 输入：candidates = [2,3,5], target = 8
- 输出：[[2,2,2,2],[2,3,3],[3,5]]
示例 3：
- 输入：candidates = [2], target = 1
- 输出：[]
哪吒的“乾坤圈”与递归
哪吒的“乾坤圈”大家都知道，一圈套一圈，无穷无尽。递归也是这样，一层套一层，直到找到答案。今天我们就用递归来解决这个问题。
递归的思路
- 基线条件：当 target 为 0 时，说明我们已经找到了一个有效的组合，将其加入结果列表中。
- 递归条件：从 candidates 中选择一个数字，减去它，然后继续递归查找剩余的目标值。
- 剪枝：如果当前数字大于 target，直接跳过，避免无效的递归。
代码实现
Java 实现：
public List<List> combinationSum(int[] candidates, int target) {
List<List> res = new ArrayList<>();
Deque deque = new ArrayDeque<>();
Arrays.sort(candidates);
dfs(res, deque, candidates, target, 0);
return res;
}
public void dfs(List<List> res, Deque deque, int[] candidates, int target, int index) {
if (target == 0) {
res.add(new ArrayList<>(deque));
return;
}
for (int i = index; i < candidates.length; i++) {
if (target - candidates[i] < 0) {
return;
}
deque.addLast(candidates[i]);
dfs(res, deque, candidates, target - candidates[i], i);
deque.removeLast();
}
} C++ 实现：
vector<vector> combinationSum(vector& candidates, int target) {
vector<vector> res;
vector deque;
sort(candidates.begin(), candidates.end());
dsf(res, deque, candidates, target, 0);
return res;
}
void dsf(vector<vector>& res, vector& deque,
vector& candidates, int target, int index) {
if (target == 0) {
res.push_back(deque);
return;
}
for (int i = index; i < candidates.size(); i++) {
if (target - candidates[i] < 0) {
return;
}
deque.push_back(candidates[i]);
dsf(res, deque, candidates, target - candidates[i], i);
deque.pop_back();
}
} 递归的“乾坤圈”
递归就像哪吒的“乾坤圈”，一圈套一圈，直到找到答案。每次递归调用都是在缩小问题的规模，直到达到基线条件。这个过程虽然看似简单，但却是解决复杂问题的利器。
坚持的意义
写代码就像修炼仙法，需要不断的练习和坚持。每一次递归调用，都是对问题的一次深入探索。只有坚持不懈，才能最终找到问题的答案。
结语
好了，今天的“仙法”就传授到这里。希望大家能从中学到递归的精髓，像哪吒一样，用“乾坤圈”解决所有难题！下次再见，记得多练习哦！
思考题：如果 candidates 中有重复元素，且每个数字只能使用一次，你会如何修改代码？欢迎在评论区分享你的思路！