leetcode-39 組合（我恨組合）

遞歸的思想：每一次的遞歸功能，我給它抽象為新找一個位，在該位上，這個數是可以變大的，以此來幫助sum變大進而匹敵 target。

這裡有意思的地方在于每次都可以用原來的數。

（盜圖~）

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> candidates, int target) {
    	if(candidates.size() < 0)
    		return {};
    	sort(candidates.begin(), candidates.end());
    	if(target < candidates[0])
    		return {};
        vector<vector<int> > result;
        vector<int> temp;
        int sum = 0;
        getBacking(result, temp, candidates, sum, 0, target);
        return result;
    }
    bool getBacking(vector<vector<int> >& result,vector<int>& temp, vector<int> nums, int sum, int k, int target){
    	// 若目前累計的數已經 比 target還要大了，我就 不額外再找一個數進行累加了
    	if(sum > target){
    		return false;
    	}else if(sum == target){
    		//如果外界讓我再找一個數累加，但是我發現目前的值就已經足夠了，不必再累加了，那麼，我們就找到了答案
    		result.push_back(temp);
    		//因為當找到答案後，再累加也沒有，是以幹脆告訴上級，活幹完了，你換下一個人吧。
    		return false;
    	}else{
    		for(int i=k;i<nums.size();i++){
    			//能到這裡意味着目前的累計和sum比target值還小，還需要一個數值累加，而我們能讓它類加的量為：nums【i】 --- nums[size-1]
    			temp.push_back(nums[i]);
    			sum += nums[i];
    			//ok，我加入了這個數了，但是，在讓該位上的數循環變成更大一點的數前，我們看看是否還需要再加一個數，讓這個數幫忙讓sum更大一些。
    			bool flag = getBacking(result, temp, nums, sum, i, target);
    			// 不管我是否需要加入新的位 來幫忙增大sum，此刻，本身所在位的數值是必須要增大的
    			temp.pop_back();
    			//記得扣除
    			sum -= nums[i];
    			if(!flag){
    				//如果我們的孩子告訴我們，娘親啊，你現在在這個位置加上的數就已經讓sum超過了target，不能再讓該位的值增大了，不然大清就亡了。
    				//so，我們要退出這個for，
    				//次外，如果目前為的值被加上後剛好等于目标，我們也不用繼續在把該位上的值增加了，因為值隻會越來越大。
    				break;
    			}
    			//如果沒退出，那就把該位上的值增大
    		}
    		//對上層調用的函數而言，新加位的所有可能都已經試過了，是以要傳回，并且讓上一層所在的數值增大
    		return true;
    	}
    }
};
int main(){
	Solution s;
	vector<int> can(1,1);
	s.combinationSum(can,1);
	return 0;
}