目录
组合的递归思路来源（核心是如何用递归实现多重循环）：
（1）用三重循环实现：3个数中选3个数（可重复),求所有可能
/*
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3
*/
for(int i=1;i<=3;i++) // 遍历1~3
{
for(int j=1;j<=3;j++) // 遍历1~3
{
for(int k=1;k<=3;k++) // 遍历1~3
{
cout<<i<<' '<<j<<' '<<k<<'\n';
}
}
}（2）用五十重循环实现：在3个数中选50个数（可重复),求所有可能，先把3重循环改造成方便复制粘贴的形式。
int a[105]; // 记录答案
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第一重循环的数
a[1] = i;
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第二重循环的数
a[2] = i;
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第三重循环的数
a[3] = i;
// 输出记录的数
for(int i=1;i<=3;i++)
{
cout<<a[i]<<' ';
}
cout<<'\n';
}
}
}
（3）生成五十个数的惯性思维程序：
int a[105]; // 记录答案
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第一重循环的数
a[1] = i;
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第二重循环的数
a[2] = i;
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第三重循环的数
a[3] = i;
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第四重循环的数
a[4] = i;
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第五重循环的数
a[5] = i;
...
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第五十重循环的数
a[50] = i;
// 输出记录的数
for(int i=1;i<=50;i++)
{
cout<<a[i]<<' ';
}
cout<<'\n';
}
}
}
}
}
}（4） 50重写起来费人，将其重复逻辑改造成递归写法
int a[105];
void dfs(int dep)
{
// 50重循环结束
if(dep > 50)
{
// 输出记录的数
for(int i=1;i<=50;i++)
{
cout<<a[i]<<' ';
}
cout<<'\n';
}
// 1~50重循环
else
{
for(int i=1;i<=3;i++) // 遍历1~3
{
// 记录第dep重的数
a[dep] = i;
// 来到下一重循环
dfs(dep+1);
}
}
} （5）上述问题改成n重循环实现：n个数中选n个，且必须是递增数据，求所有可能（n<=100)
int a[105];
void dfs(int dep, int n, int last)
{
// n重循环结束
if(dep > n)
{
// 输出记录的数
for(int i=1;i<=n;i++)
{
cout<<a[i]<<' ';
}
cout<<'\n';
}
// 1~n重循环
else
{
for(int i=last+1;i<=n;i++) // 上一个数+1 到 n
{
// 记录第dep重的数
a[dep] = i;
// 来到下一重循环
dfs(dep+1, i);
}
}
}
函数调用：dfs(1, n, 0); // last = 0，目的是令第一重循环的第一个数是1(0+1)77.组合
递归分析步骤：
单层逻辑：
1~n中取一个数，这个数还要比上一个数大
终止条件：
k层嵌套
函数参数：层数dep, 范围n, 最大个数k, 上一个数last,
一组答案的数组全局
class Solution
{
public:
vector<vector<int>> res; // 将每组结果存储
vector<int> vc; // 存储一组结果
void dfs(int dep, int n, int k, int last)
{
if(dep>k) // k重循环结束
{
res.push_back(vc);
}
else
{
for(int i=last+1; i<=n; i++) // 上一个数+1到n
{
vc.push_back(i); // 第dep层 存储一个数
dfs(dep+1, n, k, i); // 进入第dep+1层
vc.pop_back(); // 第dep层的i用过，删除，第dep准备用i++这个数
}
}
}
vector<vector<int>> combine(int n, int k)
{
dfs(1, n, k, 0);
return res;
}
};
https://leetcode.cn/problems/combinations/description/216.组合总和
题目链接：216. 组合总和 III - 力扣（LeetCode）
class Solution
{
public:
unordered_map<int, int> mp; // hash计数：用于记录数据是否用过
vector<vector<int>> res; // 将每组结果存储
vector<int> vc; // 存储一组结果
void dfs(int dep, int n, int k, int last, int sum)
{
if(dep>k) // k重循环结束
{
if(sum == n) // 判断和 是否 == n
{
res.push_back(vc);
}
}
else
{
for(int i=last+1; i<=9; i++) // 可使用数字：1~9
{
if(mp[i] == 0)
{
vc.push_back(i); // 第dep层 存储一个数
mp[i] = 1; // 把i标记为已用状态
if(sum+i <= n) // 剪枝
{
dfs(dep+1, n, k, i, sum+i); // 进入第dep+1层，当前层所计算和sum+i告知下一层
}
vc.pop_back(); // 第dep层的i用过，删除，第dep准备用i++这个数
mp[i] = 0; // 把i标记为未用状态
}
}
}
}
vector<vector<int>> combinationSum3(int k, int n)
{
dfs(1, n, k, 0, 0);
return res;
}
};17.电话号码的字母组合
题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）
难点：“23”，得到一个2，如何遍历abc，得到a，然后要得到3，得到3，如何遍历“def”。
难点解决：拿数组记录所有数字对应的字符组，字符组有了就可以根据得到的数字进行遍历。
class Solution
{
public:
vector<string> array;
// 将数字所对应的字母存储到array数组中
void alphaToArray()
{
array.push_back(""); // 位置0：空
array.push_back(""); // 位置1：空
array.push_back("abc"); // 位置2：abc
array.push_back("def"); // 位置3：def
array.push_back("ghi"); // 位置4：ghi
array.push_back("jkl"); // 位置5：jkl
array.push_back("mno"); // 位置6：mno
array.push_back("pqrs"); // 位置7：pqrs
array.push_back("tuv"); // 位置8：tuv
array.push_back("wxyz"); // 位置9：wxyz
}
vector<string> res;
void dfs(int dep, string digits, string layer)
{
if(dep > digits.size())
{
if(layer.size()>0) res.push_back(layer);
}
else
{
int pos = digits[dep-1] - '0'; // 找到按键位置
string key = array[pos]; // 得到按键字符
for(int j=0; j<key.size(); j++) // 对应按键的字符遍历
{
dfs(dep+1, digits, layer + key[j]);
}
}
}
vector<string> letterCombinations(string digits)
{
alphaToArray(); // 将2~9所对应的 字符组 按照2~9的位置 存储到array数组中
dfs(1, digits, "");
return res;
}
};