LeetCode OJ--Combination Sum **

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

给一列数，3 2 1 3 3 8 7 9 ，每个数可以重复多次，给target 7， 问可以加起来得7的所有组合。

递归，类似深搜的思想。

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > ans;
        if(candidates.size()==0)
            return ans;

        //remove duplicates
        sort(candidates.begin(),candidates.end());
        vector<int>::iterator itr = unique(candidates.begin(),candidates.end());
        candidates.resize(itr - candidates.begin());
        if(candidates[0]>target)
            return ans;

        //remove the elements great than target
        int len = candidates.size();
        while(len>=1 && candidates[len-1] > target)
            len--;
        candidates.resize(len);

        vector<int> ansPiece;
        combinationSum(candidates,ans,target,0,ansPiece);
        
        return ans;
    }
    void combinationSum(vector<int> & candidates,vector<vector<int> > &ans,int target,int pivot,vector<int> ansPiece)
    {
        if(target == 0)
        {
            ans.push_back(ansPiece);
            return;
        }
        if( target <0 ||pivot == candidates.size())
            return;

        int i = 0;
        while(target - i>=0)
        {
            if(i != 0)
                ansPiece.push_back(candidates[pivot]);
            combinationSum(candidates,ans,target - i,pivot+1,ansPiece);

            i = i + candidates[pivot];
        }
    }
};