电话号码的字母组合
（力扣 17题）
定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
代码
class Solution
{
public:
// 存放结果集
vector<vector<int>> result;
// 符合条件的结果
vector<int> path;
// targetSum：目标和，也就是题目中的n。
// k：题目中要求k个数的集合。
// sum：已经收集的元素的总和，也就是path里元素的总和。
// startIndex：下一层for循环搜索的起始位置。
void backtracking(int targetSum, int k, int sum, int startIndex)
{
// 剪枝操作
if(sum > targetSum)
{
return;
}
// 回溯结束条件
if (path.size() == k) // 取到要求的数字
{
if (targetSum == sum)
{
result.push_back(path);
}
// sum != targetSum 直接返回
return;
}
// 单层搜索过程（剪枝）
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++)
{
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n)
{
path.clear();
result.clear();
backtracking(n, k ,0 , 1);
return result;
}
};
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
代码
class Solution
{
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int> &candidates, int target, int sum, int startIndex)
{
// 递归终止条件(叶子节点)
// if (sum > target)
// return; //剪枝之后就不需要了
if (sum == target)
{
result.push_back(path);
return;
}
// 单层搜索的逻辑
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) //总集合排序之后
// 如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
{
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
// 回溯
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
result.clear();
path.clear();
if(candidates.size() == 0)
return result;
// 需要排序,剪枝
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return result;
}
};
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
组合总和
（力扣39 题）
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
代码
class Solution
{
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<bool> used(candidates.size(), false);
// 初始化
result.clear();
path.clear();
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &candidates, int target, int sum, int startIndex, vector<bool> &used)
{
if (target == sum)
{
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);
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
};
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
代码
class Solution
{
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<bool> used(candidates.size(), false);
// 初始化
result.clear();
path.clear();
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &candidates, int target, int sum, int startIndex, vector<bool> &used)
{
if (target == sum)
{
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);
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
};