40. Combination Sum II.txt

//Ìî¸ ðåøåíèå. Îñíîâíîé êîä âçÿò èç ïðîøëîé çàäà÷è. Îòëè÷èåì ÿâëÿåòñÿ òî, ÷òî âõîäÿùèé âåêòîð îòñîðòèðîâàí. 
//Òàê æå âî èçáåæàíèÿ äóáëèðîâàíèé ðåøåíèé, ïðîïóñêàåì îäèíàêîâûå çíà÷åíèÿ ÏÐÈ âûçîâå ñëåäóþùåãî ÷èñëà.(Òîëüêî êîãäà ÷èñëî ïîëíîñòüþ íå ïîäîøëî). 
class Solution {
public:
    void sol(int ind, int target, vector<int>&candidates, vector<int>&nums, vector<vector<int>>&ans) {//Ðåêóðñèâíàÿ ôóíêöèÿ.
        if (ind == candidates.size()) {//Åñëè â íàáîðå ìàêñèìàëüíîå êîë-âî ÷èñåë
            if (target == 0)//Åñëè òàðãåò = 0, çíà÷èò òàðãåò == ñóììå âñåõ ÷èñåë â âåêòîðå nums
                ans.push_back(nums);//Äîáàâëÿåì íàáîð ÷èñåë â âåêòîð îòâåòà.
            return;//Âîçâðàò íà øàã íàçàä.
        }
        if (target >= candidates[ind]) {//åñëè òàðãåò áîëüøå èëè ðàâåí 
            nums.push_back(candidates[ind]);//äîáàâëÿåì òåêóùåå ÷èñëî â âåêòîð ÷èñåë, ðàññìàòðèâàåìûõ äëÿ îòâåòà
            sol(ind + 1, target - candidates[ind], candidates, nums, ans);//âûçîâ ðåêóðñèè. Îòíèìàåì îò òàðãåòà òåêóùåå ÷èñëî
            nums.pop_back();//Êîãäà ôóíêöèÿ âåðí¸òñÿ óäàëÿåì ïîñëåäíåå ÷èñëî èç nums, ÷òîáû ïðîäîëæèòü èñêàòü åù¸ ðåøåíèÿ.
        }
        //×òîáû ðåøåíèÿ íå äóáëèðîâàëèñü, ïðîïóñêàåì îäèíàêîâûå çíà÷åíèÿ ïðè âûçîâå ñëåäóþùåãî ÷èñëà.
        while (ind < candidates.size() - 1 && candidates[ind] == candidates[ind + 1]) {
            ind++;
        }
        sol(ind + 1, target, candidates, nums, ans);//Åñëè ÷èñëî íå ïîäîøëî, âûçûâàåì ðåêóðñèþ ñî ñëåäóþùèì ÷èñëîì.
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>>ans;//Âåêòîð îòâåòà
        vector<int>nums;//âåêòîð èñïîëüçóåìûõ ÷èñåë
        sort(begin(candidates), end(candidates));//ñîðòèðóåì âõîäÿùèé âåêòîð.
        sol(0, target, candidates, nums, ans);//Âûçîâ ðåêóðñèâíîé ôóíêöèè. 1ûé ïàðàìåòð - èíäåêñ ÷èñëà â âåêòîðå candidates
        return ans;//Âîçâðàò îòâåòà
    }
};