代码随想录|回溯part 01

存在于递归函数的下方，递归与回溯相辅相成
回溯搜索法：暴力算法
适用范围：
• 组合问题：N个数里面按一定规则找出k个数的集合（无序）
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式（有序）
• 棋盘问题：N皇后，解数独等等 

理解：
1、将回溯抽象为高度有限的n叉树
宽度为集合大小，利用for循环遍历
深度为递归深度，利用递归，有终止条件

模板：
void backtracking(参数）
{
	If(终止条件){
		收集结果；
		return;
	}
	//单层搜索
	for(集合元素)
	{
		处理元素节点；
		Backtracking()递归函数；
		回溯操作；
	}
	return；
}

77.组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

要点：1、利用path储存单条路径，res储存所有路径
2、当path.size()==k时，说明满足k个数的条件，返回
3、集合中元素为1~n，利用for循环遍历
剪枝优化：判断i在循环遍历中可取的最大值
在该题中，i<=n-(k-path.size())+1
4、将节点元素放入path中
5、进行递归
6、回溯
class Solution {
public:
    vector<int>path;
    vector<vector<int>>res;
    void backtracking(int n,int k,int startindex)
    {
        if(path.size()==k)
        {
            res.push_back(path);
            return ;
        }
        for(int i=startindex;i<=n;i++)
        {
            path.push_back(i);
            backtracking(n,k,i+1);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n,k,1);
        return res;
    }
};

216.组合总和
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
	• 只使用数字1到9
	• 每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution {
public:
    vector<int>path;
    vector<vector<int>>res;
    void backtracking(int n,int k,int sum,int index)
    {
        if(path.size()==k)
        {
            if(n==sum)res.push_back(path);
            return ;
        }
        for(int i=index;i<=9;i++)
        {
            sum+=i;
            if(sum>n)
            {
                sum-=i;
                return;
            }
            path.push_back(i);
            backtracking(n,k,sum,i+1);
            sum-=i;
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(n,k,0,1);
        return res;   
    }
};

17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

要点：1、利用常量字符串实现数字到字母的映射
2、不同集合间的组合，运用index来记录处于哪一个集合，当index==digits.size()时说明index到了最后一个集合，应当结束返回

class Solution {
public:
    const string letter[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    string s;
    vector<string> res;
    void backtracking(string digits,int index)//index指digits的位数
    {
        if(index==digits.size())
        {
            res.push_back(s);
            return ;
        }
        int t=digits[index]-'0';
        string k=letter[t];//取出对应字符集
        for(int i=0;i<k.size();i++)
        {
            s.push_back(k[i]);
            backtracking(digits,index+1);
            s.pop_back();
        }
        return;
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)//判断是否为空
        {
            res.clear();
            return res;
        }
        backtracking(digits,0);
        return res;
    }
};