39. Combination Sum.txt

//Îïòèìàëüíîå ðåøåíèå 100% runtime 50% memory
//Ïî ñìûëñó òîæå ñàìîå ÷òî è ìî¸ ðåøåíèå :)
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, target - candidates[ind], candidates, nums, ans);//âûçîâ ðåêóðñèè. Îòíèìàåì îò òàðãåòà òåêóùåå ÷èñëî
            nums.pop_back();//Êîãäà ôóíêöèÿ âåðí¸òñÿ óäàëÿåì ïîñëåäíåå ÷èñëî èç nums, ÷òîáû ïðîäîëæèòü èñêàòü åù¸ ðåøåíèÿ.
        }
        sol(ind + 1, target, candidates, nums, ans);//Åñëè ÷èñëî íå ïîäîøëî, âûçûâàåì ðåêóðñèþ ñî ñëåäóþùèì ÷èñëîì.
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {//Îñíîâíàÿ ôóíêöèÿ
        int i,j,n=candidates.size();//Ïî èäåå ëèøíåå
        vector<vector<int>>ans;//Âåêòîð îòâåòà
        vector<int>nums;//âåêòîð èñïîëüçóåìûõ ÷èñåë
        sol(0, target, candidates, nums, ans);//Âûçîâ ðåêóðñèâíîé ôóíêöèè. 1ûé ïàðàìåòð - èíäåêñ ÷èñëà â âåêòîðå candidates
        return ans;//Âîçâðàò îòâåòà
    }
};


//Ìî¸ ðåøåíèå beast 77% runtime, 53% memory.  ïðèíèïå íåïëîõî (ïî÷òè ëó÷øèé).
//Îáû÷íàÿ ðåêóðñèÿ. Ïåðåáîð âñåõ âàðèàíòîâ. Åñëè â êîíöå ÷èñëî íå ïîäîøëî, áîëüøå íå èñïîëüçóåì åãî (ïàðàìåòð i).
//
class Solution {
    void recursion(vector<int>& candidates, int target, vector<vector<int>>& answer, vector<int>& tempNum, int sum, int count) {
        if (sum == target)
            answer.push_back(tempNum);
        else if (sum > target) {
            return;
        }
        else {
            for (int i = count; i < candidates.size(); i++) {
                tempNum.push_back(candidates[i]);
                sum += candidates[i];
                recursion(candidates, target, answer, tempNum, sum, i);
                sum -= candidates[i];
                tempNum.pop_back();
            }
        }
        return;
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> answer;
        vector<int> tempNum;
        recursion(candidates, target, answer, tempNum, 0, 0);
        return answer;
    }
};