您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 筆記：Combination Sum（組合總和）無限取用 DFS

編輯：關於C++

題目大意

給定無重複的正整數候選集 C 和目標 T，找出所有組合使和為 T。候選數可無限次使用。組合內非降序，解集無重複。

DFS 遞歸策略

排序候選數組。遞歸函數參數包含當前起始索引 start、當前和 sum。從 start 開始嘗試選擇候選數，選擇後遞歸調用仍傳 i（而非 i+1），允許重複使用。剪枝：sum > target 返回；candidates[i] > target - sum break。

代碼實現

class Solution {
    vector<vector<int>> res;
    void comb(vector<int>& cand, int idx, int sum, int target, vector<int>& path) {
        if (sum > target) return;
        if (sum == target) { res.push_back(path); return; }
        for (int i = idx; i < cand.size(); ++i) {
            if (cand[i] > target - sum) break;
            path.push_back(cand[i]);
            comb(cand, i, sum + cand[i], target, path); // i 允許重複用
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        comb(candidates, 0, 0, target, path);
        return res;
    }
};