力扣39. 组合总和

回溯

• 思路：
  • 定义递归函数 dfs(candidates, target, idx)，表示当前 candidates 在 idx 位，还剩 target 需要组合；
  • 递归终止条件：
    • target <= 0；
      • target == 0 时，将该组合存入结果数组；
    • candidates 元素已经用完，idx = candidates.size()；
  • 在当前函数中，可以：
    • 跳过 candidates[idx] 元素进行组合，即 dfs(candidates, target, idx + 1) ；
    • 也可以使用 candidates[idx] 元素进行组合（因为可以使用重复元素），即 dfs(candidates, target - candidates[idx], idx)

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return result;
    }

private:
    void dfs(std::vector<int>& candidates, int target, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            result.emplace_back(item);
            return;
        }
        dfs(candidates, target, idx + 1);
        if (target - candidates[idx] >= 0) {
            item.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], idx);
            item.pop_back();
        }
    }

private:
    std::vector<std::vector<int>> result;
    std::vector<int> item;
};