Комбинация Сумма

Question

Учитывая набор чисел кандидатов (С) и целевым номером (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; (То же, что и цель, сохранить комбинацию)
      • Сумма = 1 + 1 + 1 + 2; (Больше, чем цель, не больше номера для добавления)
    • Sum = 1 + 1 + 2; (Сохранить комбинацию, больше не нужно добавить)
  • Sum = 1 + 2;
    • Sum = 1 + 2 + 2; (Большего размера, больше не число)
• Сумма = 2;
  • Sum = 2 + 2; (Сохранить, это последняя рекурсия)