[ 回溯 ] 组合总和

39. 组合总和 - 力扣(LeetCode) (leetcode-cn.com)

组合总和

  • DFS
  • 回溯
  • 剪枝
  • 遇到可以重复取数怎么办?
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    void DFS(vector<int>& candidates, int target, int sum, int index) {
        //剪枝
        if (sum > target) return;
        if (sum == target) {
            ans.emplace_back(path);
            return;
        }
        for (int i = index; i < candidates.size(); ++i) {
            sum += candidates[i];
            path.emplace_back(candidates[i]);
            // 遇到可以重复取数怎么办?
            // 我们重新取i,即可。不可以重复取数就i+1跳过重复。
            DFS(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        DFS(candidates, target, 0, 0);
        return ans;
    }
};
上一篇:最新Java笔试题分享,40张图文详解,我就不信你还参透不了并发编程


下一篇:LeetCode39 组合总和