给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
//回溯算法求组合问题：
//1.首先构建数组存放要返回的值
//2.判断递归结束的条件
//3.for循环遍历（注意看清楚从哪个位置开始遍历）
//4.递归
//5.回溯
//回溯相当于进行n层for循环
class Solution {
public:
vector<int>path;
vector<vector<int>>ret;
void backtracking(int n,int k,int j)
{
? //1.确定终止条件
? if(path.size()==k)
? {
? ret.push_back(path);
? return ;
? }
? //2.for循环+递归相当于进行n层for循环
? //每次递归完之后记着回退到上一个位置
? for(int i=j;i<=n;i++)
? {
? path.push_back(i);
? backtracking(n,k,i+1);
? path.pop_back();
? }
}
vector<vector<int>> combine(int n, int k) {
? backtracking(n,k,1);
? return ret;
}
};
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
本题与上面的77题组合问题非常相似，就是组合问题加上限制条件即可，这次不光要path.size==k,还要使path数组的和为n,因此我们只要对上面的组合的代码加一些限制即可
class Solution {
public:
//定义一个二维数组ret用来存放最终要返回的结果
vector<vector<int>>ret;
//path一位数组用来存放每次遍历的值
vector<int>path;
//定义回溯函数backtracking,startIndex代表每次开始时的下标，k为数字个数，m为和，sum为数组path的各个元素之和
void backtrack(int startIndex,int k,int n,int sum)
{
//与基础组合不同，这里需要强化条件，数量相等时，则进一步判断path的大小与题目要求的大小是否相等
? if(path.size()==k)
? {
//如果path数组的大小与题目要求的数组大小相同，则将该数组尾插到ret中
? if(sum==n)
? {
? ret.push_back(path);
? }
//不相等或者尾插后return，返回到上一层
? return;
? }
//回溯算法的经典环节，for循环环节，
? for(int i=startIndex;i<=9;i++)
? {
//每次计算sum的值
? sum+=i;
//如果sum>n,直接返回，枝剪
? if(sum>n)
? break;
//入值
? path.push_back(i);
//递归
? backtrack(i+1,k,n,sum);
回溯
? sum-=i;
? path.pop_back();
? }
}
vector<vector<int>> combinationSum3(int k, int n) {
? path.clear();
? ret.clear();
? backtrack(1,k,n,0);
? return ret;
}
};
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 g
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
求出数组中和为target的元素：即循环遍历数组中的元素，找到和为target的元素，注意这一次startIndex从i开始取，即当前元素可以取重复的，然后注意递归终止条件的判断，本次递归终止条件为sum>target终止，当sum==target时，让path进入到ret数组中
//组合问题的套路：回溯算法
//1.确定函数参数
//2.确定递归终止条件
//3.for循环进行回溯
class Solution {
public:
vector<vector<int>>ret;
vector<int>path;
void backtrack(vector<int>&candidates,int target,int startIndex,int sum)
{
? //当target==sum时，返回
? if(sum>target)
? return;
? if(target==sum)
? {
? ret.push_back(path);
? return;
? }
? for(int i=startIndex;i<candidates.size();i++)
? {
? sum+=candidates[i];
? //sum>taarge时，直接剪枝进行返回
? path.push_back(candidates[i]);
? //递归回溯过程
? backtrack(candidates,target,i,sum);
? path.pop_back();
? sum-=candidates[i];
? }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
? path.clear();
? ret.clear();
? backtrack(candidates,target,0,0);
? return ret;
}
};
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xz2Digw8-1630925647001)(http://style.iis7.com/uploads/2021/09/21230060075.png)]
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
本题如果不用回溯算法将会非常难算
class Solution {
public:
//首先利用哈希映射将2到9映射到一个二维数组中
string stringMap[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string>ret;
string path;
void backtrack(string&digits,int index)
{
? if(digits.size()==path.size())
? {
? ret.push_back(path);
? return;
? }
? int n=digits[index]-48
