leetcode筆記：Combination Sum

一. 題目描述

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

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

Note:
? All numbers (including target) will be positive integers.
? Elements in a combination (a1; a2; … ; ak) must be in non-descending order. (a1<=a2<=…<= ak).
? The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, A solution set is:

[7]
[2, 2, 3]

二. 題目分析

題目大意是：有一個正整數集合C，和一個正整數目標T。現從C中選出一些數，使其累加和恰好等於T（C中的每個數都可以取若干次），求所有不同的取數方案。一道典型的DFS題。

三. 示例代碼

// 來源：http://blog.csdn.net/doc_sgl/article/details/12283675
#include 
#include 
#include 
using namespace std;

class Solution 
{
private:
    void comb(vector candidates, int index, int sum, int target, vector> &res, vector &path)
    {
        if(sum>target)return;
        if(sum==target){res.push_back(path);return;}
        for(int i= index; i > combinationSum(vector &candidates, int target) {
        // Note: The Solution object is instantiated only once.
        sort(candidates.begin(),candidates.end());
        vector> res;
        vector path;
        comb(candidates,0,0,target,res,path);
        return res;
    }
};

四. 小結

最近比較忙碌，只能先借鑒別人的代碼進行學習，後續要深入研究。