程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Combination Sum

leetcode筆記:Combination Sum

編輯:C++入門知識

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;
    }
};

四. 小結

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved