77.组合

// 回溯本质都可以视为N叉树
class Solution {
public:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path;// 存放符合条件的结果
    void recursive(int n,int k,int startIndex){
    	// 递归终止条件
        if(path.size() == k){
            result.push_back(path);
            return;
        }
        // for循环，横向遍历[n-(k-path.size())+1,此判断为剪枝优化]
        for(int i = startIndex;i<=(n - (k-path.size()) + 1);++i){
            path.emplace_back(i); // 添加
            recursive(n,k,i+1); // 递归进行纵向遍历
            path.pop_back(); // 回溯
        }
    }
    vector<vector<int>> combine(int n, int k) {
        recursive(n,k,1);
        return result;
    }
};

17.电话号码的字母组合

class Solution {
public:
    vector<string> result;
    string path;
    vector<string> container{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void backtracking(string &digits,int startIndex){
    	// 递归终止条件
        if(path.size() == digits.size()){
            result.push_back(path);
            return;
        }
		// for循环横向遍历digits[startIndex]
        for(int i = 0;i<container[digits[startIndex] - '0'].size();++i){
            path.push_back(container[digits[startIndex]-'0'][i]); // 插入数据
            backtracking(digits,startIndex+1);	// 递归纵向遍历digits
            path.pop_back(); // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        backtracking(digits,0);

        return result;
    }

39.组合总和

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target,int startIndex,int sum){
       	// 递归终止条件
        if(sum > target){
            return;
        }
        if(sum == target){
            result.push_back(path);
            return;
        }
		// for循环横向遍历candidates
        for(int i = startIndex;i<candidates.size();++i){
            path.push_back(candidates[i]);
            sum+=candidates[i];

            backtracking(candidates,target,i,sum);// 递归纵向遍历，始终传入i，无需+1
			// 回溯
            path.pop_back();
            sum-=candidates[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0,0);   
        return result;
    }
};

40.组合总和II

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;
        }
        // 使用求和的校验进行剪枝
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            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); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            // 回溯
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};

216.组合总和III

class Solution {
public:
    vector<vector<int>> result; // 储存符合条件的结果集合
    vector<int> path;	// 储存符合条件的结果
    void backtracking(int k,int n,int sum,int startIndex){
    	// 递归终止条件
        if(sum > n) return;
        if(path.size() == k){
            if(sum == n)result.push_back(path);
            return;
        }
		// for循环横向遍历
        for(int i = startIndex;i<=9-(k-path.size()) +1;++i){
            sum+=i;
            path.emplace_back(i);
            backtracking(k,n,sum,i+1);// 递归
            // 回溯
            sum-=i;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,0,1);
        return result;
    }
};