LeetCode: Combination Sum

题目

https://oj.leetcode.com/problems/combination-sum/

分析

DFS,之前总结过很多道同类型的题。

代码

class Solution
{
public:
	vector<vector<int>> combinationSum(vector<int> &candidates, int target)
	{
		if (candidates.size() == 0)
			return res;
		this->candidates = candidates;
		sort(this->candidates.begin(), this->candidates.end());
		vector<int> solution;

		DFS(solution, 0, target);

		return res;
	}
	void DFS(vector<int> &solution, int start, int target)
	{
		if (target == 0)
			res.push_back(solution);
		else
		{
			for (int i = start; i < candidates.size() && candidates[i] <= target; i++)
			{
				solution.push_back(candidates[i]);
				DFS(solution, i, target-candidates[i]);
				solution.pop_back();
			}
		}
	}
private:
	vector<int> candidates;
	vector<vector<int>> res;
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40479161

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();