class Solution {
private:
    vector<vector<int>> result;//存放符合條件的結果結合
    vector<int> path;//存放符合條件的單一結果
    void backtracking(int n, int k, int startIndex) {
        //回溯的終止條件:如果path數組的大小剛好等於k，說明找到了一個符合條件的結果集，存放進去
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        //for(int i=startIndex; i<=n; i++) {
            /*這個循環其實可以進行剪枝優化，因為你要求k個數的結合，那你之多也就只能遍歷到結合剩下k個元素的位置，後面的遍歷都是沒有意義的，優化如下*/
        for (int i=startIndex; i<=(n-(k-path.size())+1); i++) {
            path.push_back(i);//處理節點
            backtracking(n, k, i+1);//遞歸，一直往裡放，直到滿足終止條件結束
            path.pop_back();//回溯，撤銷處理的節點
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n, k, 1);
        return result;
    }
};

class Solution {
private:
    vector<vector<int>> result; // 用來存放結果
    vector<int> path; // 用來存放一個滿足條件的路徑

    void backtrackint(int k, int n, int sum, int startIndex) {
        if (sum == n) { // 如果和為n滿足了條件
            if (path.size() == k) // 如果滿足k個數
                result.push_back(path); // 將滿足要求的一個路徑path放進去
            return;
        }
        if (sum > n) // 進行剪枝，如果當前的已經大於n了，再往下比n更大
            return;

        for (int i = startIndex; i <= 9; i++) {
            path.push_back(i); // 處理當前
            sum += i;
            backtrackint(k, n, sum, i+1); // 遞歸
            sum -= i;
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtrackint(k, n, 0, 1);
        return result;
    }
};

class Solution {
private:
    unordered_map<int, string> letterMap = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"},{8, "tuv"}, {9, "wxyz"}};
public:
    vector<string> result;
    string s;
    void backtracking(const string& digits, int index) {
        if (index == digits.size()) {//每個組合的字元串當中有digits.size()個元素
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';//將index位置對應的字元轉換成Int
        string letters = letterMap[digit]; //取出digit對應的字符集
        for (int i=0; i<letters.size(); i++) {
            s.push_back(letters[i]);
            backtracking(digits, index+1); //遞歸，注意index+1，要處理下一個數字了
            s.pop_back(); //回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        s.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        if (sum > target) // 因為數組中元素都是正整數，所以可以剪枝
            return;
        
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) { // &&後面的是剪枝，意思是在當前層中，如果下一層的sum（就是本層的sum加上candidates[i]）已經大於target了，就沒必要繼續往下了
            path.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, sum, i); // 這裡的i是重點！！！體現了可以重複！！！
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        if (candidates.empty())
            return {};
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};
// 求和問題中，排序之後加剪枝是常見的套路！
// 什麼時候用startIndex，什麼時候不用：如果是一個集合來求組合的話，就需要startIndex；如果是多個集合取組合，各個集合之間相互不影響，那麼就不用startIndex
// 元素可被無限重複選取表現在程式碼里
// 剪枝方法

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i=startIndex; i<candidates.size() && (sum + candidates[i]) <= target; i++) {
            /*如果candidates[i] == candidates[i-1]並且used[i-1] == 1的話，說明元素在同一個樹枝里使用過，這是允許的
            *如果candidates[i] == candidates[i-1]並且used[i-1] == 0的話，說明元素在同一樹層里重複了，這是不允許的，要進行去重
            */
            if (i>0 && candidates[i] == candidates[i-1] && used[i-1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i+1, used); // 這裡是i+1不是i
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        vector<bool> used(candidates.size(), false); // 用這數組來進行去重
        sort(candidates.begin(), candidates.end()); // 先把數組排序，讓相同的元素排在一起，這樣才能後面去重
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};