小旭讲解 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:

target

Example 1:

<strong>Input:</strong> candidates = <code>[2,3,6,7], </code>target = <code>7</code>,
<strong>A solution set is:</strong>
[
  [7],
  [2,2,3]
]

Example 2:

<strong>Input:</strong> candidates = [2,3,5]<code>, </code>target = 8,
<strong>A solution set is:</strong>
[
  [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/回溯法