哪吒的“乾坤圈”与递归：如何用代码找到所有组合？

大家好，我是哪吒，今天不闹海，也不打龙王，咱们来聊聊递归和组合问题。你可能会问，哪吒你一个神仙，怎么还搞起代码来了？嘿，这不都是为了给你们这些凡人传授点“仙法”嘛！

问题描述

给你一个无重复元素的整数数组 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
• 输出：[]

哪吒的“乾坤圈”与递归

哪吒的“乾坤圈”大家都知道，一圈套一圈，无穷无尽。递归也是这样，一层套一层，直到找到答案。今天我们就用递归来解决这个问题。

递归的思路

1. 基线条件：当 target 为 0 时，说明我们已经找到了一个有效的组合，将其加入结果列表中。
2. 递归条件：从 candidates 中选择一个数字，减去它，然后继续递归查找剩余的目标值。
3. 剪枝：如果当前数字大于 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 中有重复元素，且每个数字只能使用一次，你会如何修改代码？欢迎在评论区分享你的思路！