組合薩姆

Question

給定一組候選數（C）和目標數（T）的，找到在C中的所有唯一組合，其中所述候選號碼款項T.

相同重複數目可以選自C無限選擇次數。

All numbers (including target) will be positive integers. 
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). 
The combinations themselves must be sorted in ascending order. 
CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1) 
The solution set must not contain duplicate combinations. 

實施例， 鑑於候選集2,3,6,7和目標7， 的溶液組是：

[2, 2, 3] [7]

溶液代碼是：

class Solution { 
    public: 

    void doWork(vector<int> &candidates, int index, vector<int> &current, int currentSum, int target, vector<vector<int> > &ans) { 
     if (currentSum > target) { 
      return; 
     } 
     if (currentSum == target) { 
      ans.push_back(current); 
      return; 
     } 
     for (int i = index; i < candidates.size(); i++) { 
      current.push_back(candidates[i]); 
      currentSum += candidates[i]; 

      doWork(candidates, i, current, currentSum, target, ans); 

      current.pop_back(); 
      currentSum -= candidates[i]; 
     } 

    } 

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) { 
     vector<int> current; 
     vector<vector<int> > ans; 
     sort(candidates.begin(), candidates.end()); 
     vector<int> uniqueCandidates; 
     for (int i = 0; i < candidates.size(); i++) { 
      if (i == 0 || candidates[i] != candidates[i-1]) { 
       uniqueCandidates.push_back(candidates[i]); 
      } 
     } 
     doWork(uniqueCandidates, 0, current, 0, target, ans); 
     return ans; 
    } 
}; 

現在，雖然我可以通過舉例來了解解決方案，但是我怎麼能夠提出這樣的解決方案。主要工作在這個功能：

for (int i = index; i < candidates.size(); i++) { 
     current.push_back(candidates[i]); 
     currentSum += candidates[i]; 

     doWork(candidates, i, current, currentSum, target, ans); 

     current.pop_back(); 
     currentSum -= candidates[i]; 
    } 

請告訴我如何理解上述代碼以及如何去思考這個解決方案。我可以解決基本的遞歸問題，但這些看起來遙不可及。謝謝你的時間。

Answer 1

那麼代碼通常做的就是：

1. 排序給定的遞增的順序號。
2. 刪除集合中的重複項。
3. 對於組中的每個數字：
   • 不斷增加相同數量，直到總和或者大於或等於所述目標。
   • 如果相等，則保存組合。
   • 如果它更大，請刪除最後添加的數字（返回上一步驟），並開始將該集合中的下一個數字添加到總和中。

對於理解遞歸，我想先從最簡單的情況。讓我們來看看，例如： Candidates: { 2, 2, 1 } Target: 4

排序和刪除重複項變更設定爲{1，2}。遞歸順序將爲：

• Sum = 1;
  • Sum = 1 + 1;
    • Sum = 1 + 1 + 1;
      • Sum = 1 + 1 + 1 + 1; （與目標相同，保存組合）
      • Sum = 1 + 1 + 1 + 2; （大於目標，不再增加數字）
    • Sum = 1 + 1 + 2; （保存組合，不再需要添加數字）
  • Sum = 1 + 2;
    • Sum = 1 + 2 + 2; （較大的，沒有更多的數）
• 薩姆= 2;
  • Sum = 2 + 2; （保存，這是最後一次遞歸）