1. 題目鏈接：39. 組合總和

2. 題目描述：

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

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

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

示例 1：

輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。

示例 2：

輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

輸入: candidates = [2], target = 1
輸出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

3. 解法：

3.1 算法思路：

candidates的所有元素互不相同，因此我們在遞歸狀態(tài)時只需要對每個元素進(jìn)行如下判斷：

1. 跳過，對下一個元素進(jìn)行判斷
2. 將其添加到當(dāng)前狀態(tài)中，我們在選擇添加當(dāng)前元素時，之后仍可以繼續(xù)選擇當(dāng)前元素（可以重復(fù)選同一元素）

因此，我們在選擇當(dāng)前元素并向下傳遞下標(biāo)時，應(yīng)該直接傳遞當(dāng)前元素下標(biāo)

3.2 遞歸函數(shù)流程：

1. 結(jié)束條件：
   1. 當(dāng)前需要處理的元素下標(biāo)越界
   2. 當(dāng)前狀態(tài)的元素和已經(jīng)和目標(biāo)值相同
2. 跳出當(dāng)前元素，當(dāng)前狀態(tài)不變，對下一個元素進(jìn)行處理
3. 選擇當(dāng)前元素添加至當(dāng)前狀態(tài)，并保留狀態(tài)繼續(xù)對當(dāng)前元素進(jìn)行處理，遞歸結(jié)束時撤銷添加操作

3.3 C++算法代碼：

class Solution {int aim; // 目標(biāo)和vector<int> path; // 當(dāng)前路徑vector<vector<int>> ret; // 結(jié)果集
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {aim = target; // 初始化目標(biāo)和dfs(candidates, 0, 0); // 從第一個元素開始搜索return ret; // 返回結(jié)果集}void dfs(vector<int>& candidates, int pos, int sum) {if (sum == aim) { // 如果當(dāng)前路徑的和等于目標(biāo)和ret.push_back(path); // 將當(dāng)前路徑加入結(jié)果集return; // 結(jié)束當(dāng)前遞歸}if (sum > aim || pos == candidates.size()) { // 如果當(dāng)前路徑的和大于目標(biāo)和或者已經(jīng)遍歷完所有元素return; // 結(jié)束當(dāng)前遞歸}for (int k = 0; k * candidates[pos] + sum <= aim; k++) { // 遍歷當(dāng)前元素的所有可能組合if (k) path.push_back(candidates[pos]); // 如果當(dāng)前元素被使用，將其加入當(dāng)前路徑dfs(candidates, pos + 1, sum + k * candidates[pos]); // 繼續(xù)搜索下一個元素}for (int k = 1; k * candidates[pos] + sum <= aim; k++) { // 回溯，移除當(dāng)前元素path.pop_back();}}
};