[代码随想录21回溯]组合问题，电话号码的字母组合问题

前言

 回溯的提出是解决循环问题，回溯的提出就是为了解决排列和组合问题，以及多层遍历问题，因为如果遍历的层数越多我们的效率就会越低，回溯加上剪枝能很好解决这个问题。

题目链接

77. 组合 - 力扣（LeetCode）

216. 组合总和 III - 力扣（LeetCode）

17. 电话号码的字母组合 - 力扣（LeetCode）

一、组合

 思路：规定一个路径集合，和一个结果集合，用if去判断路径，用for循环去横向和纵向去加载路径。

剪枝优化的思路：去除掉无效的长度。

private:vector<vector<int>> res;vector<int>path;void backtrancing(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);backtrancing(n,k,i+1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backtrancing(n,k,1);return res;}

private:vector<vector<int>> res;vector<int>path;void backtrancing(int n,int k,int startIndex){if(path.size()==k){res.push_back(path);return;}//剪枝优化一下for(int i=startIndex;i<=n-(k-path.size())+1;i++){path.push_back(i);backtrancing(n,k,i+1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backtrancing(n,k,1);return res;}

 

二、组合总和

 思路：

三、电话号码的字母组合

思路：