原題出于leetcode第39題https://leetcode.cn/problems/combination-sum/description/題目如下：

給你一個(gè) 無重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個(gè)目標(biāo)整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個(gè) 數(shù)字可以 無限制重復(fù)被選取 。如果至少一個(gè)數(shù)字的被選數(shù)量不同，則兩種組合是不同的。

對(duì)于給定的輸入，保證和為 target 的不同組合數(shù)少于 150 個(gè)。

1.樹型結(jié)構(gòu)

2.代碼

這里用到的剪枝與組合總和Ⅲ中sum類似，不再贅述

class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& candidates,int target,int sum,int startindex){if(sum>target)return ;if(sum==target){result.push_back(path);return;}for(int i=startindex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}return ;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {path.clear();result.clear();backtracking(candidates,target,0,0);return result;}
};