小旭讲解 LeetCode 39. Combination Sum 回溯法

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

Given a set of candidate numbers (candidates(without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题解

讲义

考察知识点

      回溯法(深度优先搜索,Depth-First Search)

回溯法搜索轨迹示意图

代码

class Solution {
public:
    vector<vector <int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector <int>> result{};
        vector<int> candidate{};
        sort(candidates.begin(), candidates.end());
        sum(result, candidates, target, candidate, 0);
        return result;
    }
    
    void sum(vector<vector <int>>& result, vector<int>& candidates, int target, vector</int><int>& candidate, int level) {
        // up to the target
        if (target == 0) {
            result.push_back(candidate);
            return;
        }
        for (int i = level; i < candidates.size() && candidates[i] <= target; ++i) {
            candidate.push_back(candidates[i]);
            sum(result, candidates, target - candidates[i], candidate, i);
            candidate.pop_back();
        }
    }
};

文章来源:胡小旭 => 小旭讲解 LeetCode 39. Combination Sum 回溯法

题解视频背景音乐:《Sad Angel》

延伸阅读:zh.wikipedia.org/wiki/回溯法


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...

发表评论

电子邮件地址不会被公开。