陈中正的网络日志

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

Categories:  OJ题解 

« LeetCode: Combination Sum II 配置GDB支持STL调试 »