leetcode 39. Combination Sum (dfs,求所有的组合,和为定值,每个数可以重复用)

Posted by 111qqz on Thursday, April 13, 2017

TOC

Given a set of candidate numbers (C) (without duplicates) 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.
  * The solution set must not contain duplicate combinations.

题意:给n个数,求所有的组合,和为定值,每个数可以重复用)

思路:。。。。一开始用顺着枚举子集的思路。。。发现。。并不好搞。。。?还不如直接dfs…

/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 00时06分12秒
File Name :39.cpp
************************************************ */
class Solution {
public:

    vector<vector<int> >res;
    vector<int>tmp;
    int n;
    //思路:dfs
    void dfs( int start,int cur,vector<int> &nums)
    {
    if (cur==0)
    {
        res.push_back(tmp);
        return ;
    }
    else if (cur<0) return;
    else
    {
        for ( int i = start ; i < n ; i++)
        {
        tmp.push_back(nums[i]);
        dfs(i,cur-nums[i],nums);
        tmp.erase(tmp.begin()+tmp.size()-1);
        }
    }
    }
	
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
    n = nums.size();
    if (n==0) return res;
    dfs(0,target,nums);
    return res;
    }
};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付