原题

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)

回溯法搜索轨迹示意图

代码

[code lang=”cpp”] 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(); } } }; [/code]

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

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

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

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.