Day28 17电话号码的字母组合 39组合求和 40组合求和II

17 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

         因为输入的数字的数量是不确定的，所以for循环的次数也是不确定的，这里就需要用到回溯的方法了。

         一般回溯里面，递归都是深度，for循环都是宽度。注意本题的index和之前两道题的index不太一样，因为本题不是从同一个集合里面取，而是从多个集合里面取。同时for循环的起始位置是0，因为此时不存在从同一个集合里面取相同的数的问题了。

class Solution {
private:
    //记录对应的关系
    const string letterMap[10] = {
        " ",
        " ",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    vector<string> result; //存放结果
    string s; //存放字符串
    void backtracking(string digits, int index) {
        if(index == digits.size()) { //index表示的是第几个数字，数字等于数字大小就停止
            result.push_back(s);
            return;
        }
        int digit = digits[index]-'0'; //将index转换为“23”里的数字
        string letters = letterMap[digit]; //根据数字在哈希表里面找字符串
        for(int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]); //处理
            backtracking(digits,index+1); //递归
            s.pop_back(); //回溯
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        result.clear();
        if(digits.size()==0) return result; //特殊处理以下等于0的时候
        backtracking(digits, 0);
        return result;
    }
};

        本题也可以将回溯隐含在函数中，但是不建议这么写，不直观。

// 版本二
class Solution {
private:
        const string letterMap[10] = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
        };
public:
    vector<string> result;
    void getCombinations(const string& digits, int index, const string& s) { // 注意参数的不同
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            getCombinations(digits, index + 1, s + letters[i]);  // 注意这里的不同
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        getCombinations(digits, 0, "");
        return result;

    }
};

 39 组合求和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。

 这道题与之前那题的不同之处在于数字是题目给的，并且可以重复，总的来说都差不多。

 注意因为可以重复，所以递归函数里不用i+1而直接是i

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex) {
        if(target < 0) return;
        if(target == 0) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            target -= candidates[i];
            backtracking(candidates, target, i); //这里不需要i+1了因为可以重复的取
            target += candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0);
        return result;
    }
};

         这里可以进行剪枝操作，对这个数组排完序以后，如果前面的比target大了，那么后面也就不用看了：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex) {
        if(target < 0) return;
        if(target == 0) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size() && (target-candidates[i])>=0; i++) {
            path.push_back(candidates[i]);
            target -= candidates[i];
            backtracking(candidates, target, i); //这里不需要i+1了因为可以重复的取
            target += candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, 0);
        return result;
    }
};

 40 组合求和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

本题与上一题的不同之处就是给的数组里面有重复的元素，导致后面可能重复利用这个元素，但是还不能有重复的组合。

         这里利用一个used数组，里面存放布尔型数据，如果是1就说明这个数用过。首先对题目给的数组进行排序，去重有两种形式：树层去重和树枝去重，显而易见，我们不需要数值去重，但是需要树层去重，如果此时遍历的元素和上一个相同，并且上一个元素没有被使用过（如果使用过的话说明是树枝去重了，没有回溯的话used就不会重新被置为false），此时证明正在访问的元素是回溯以后的，并不是树枝，所以直接跳过就好了。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex, vector<bool> used) {
        if(target < 0) return;
        if(target == 0) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size()&&(target-candidates[i])>=0; i++) {
            if(i>0 && candidates[i]==candidates[i-1] && used[i-1] == false) continue;
            path.push_back(candidates[i]);
            target -= candidates[i];
            used[i] = true;
            backtracking(candidates, target, i+1, used); 
            used[i] = false;
            target += 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, used);
        return result;
    }
};