代码随想录算法训练营第二十三天| 39. 组合总和

本文主要是介绍代码随想录算法训练营第二十三天| 39. 组合总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

39. 组合总和

题目：

给你一个 无重复元素 的整数数组 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

思路：

回溯思路

1. 初始化结果列表：我们需要一个列表来存储所有的组合结果。

2. 排序候选数组：虽然题目中没有要求，但对候选数组进行排序可能会有助于优化算法，比如在递归中可以提前停止搜索。

3. 定义递归函数：递归终止条件：

   • • 如果 target == 0，说明找到了一个符合条件的组合，将其添加到结果列表中。
     • 如果 target < 0，则当前组合不满足条件，直接返回。
   • 递归过程：
     • 遍历候选数组，从start_index开始，每个数字都可以多次选取。
     • 将当前候选数字添加到组合中，更新目标值为 target - candidates[i]。
     • 递归调用函数继续寻找组合。
     • 回溯：移除组合中的最后一个数字，尝试下一个候选数字。

上代码：

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> result;   // 存储所有符合条件的组合vector<int> current_combination;  // 当前组合// 调用递归函数开始回溯backtrack(candidates, target, current_combination, result, 0);return result;}private:void backtrack(vector<int>& candidates, int target, vector<int>& current_combination, vector<vector<int>>& result, int start_index) {if (target == 0) {// 找到一个符合条件的组合，将其添加到结果中result.push_back(current_combination);return;}if (target < 0) {// 当前组合不满足条件，返回return;}for (int i = start_index; i < candidates.size(); ++i) {// 选择当前候选数字current_combination.push_back(candidates[i]);// 递归调用继续搜索，target 减去当前候选数字，start_index 保持不变以允许重复选取backtrack(candidates, target - candidates[i], current_combination, result, i);// 回溯：移除当前组合中的最后一个数字current_combination.pop_back();}}
};

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

class Solution {
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> result;   // 存储所有符合条件的组合vector<int> current_combination;  // 当前组合sort(candidates.begin(), candidates.end());  // 对候选数组进行排序// 调用递归函数开始回溯backtrack(candidates, target, current_combination, result, 0);return result;}private:void backtrack(vector<int>& candidates, int target, vector<int>& current_combination, vector<vector<int>>& result, int start_index) {if (target == 0) {// 找到一个符合条件的组合，将其添加到结果中result.push_back(current_combination);return;}for (int i = start_index; i < candidates.size(); ++i) {// 跳过重复的元素if (i > start_index && candidates[i] == candidates[i - 1]) continue;// 如果当前数字大于目标值，直接跳过后续的循环if (candidates[i] > target) break;// 选择当前候选数字current_combination.push_back(candidates[i]);// 递归调用继续搜索，target 减去当前候选数字，start_index + 1 保证每个数字只能使用一次backtrack(candidates, target - candidates[i], current_combination, result, i + 1);// 回溯：移除当前组合中的最后一个数字current_combination.pop_back();}}
};

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

class Solution {
public:vector<vector<string>> partition(string s) {vector<vector<string>> result;  // 存储所有的划分方案vector<string> current_partition;  // 当前的回文子串组合// 调用递归函数开始回溯backtrack(s, 0, current_partition, result);return result;}private:// 判断一个子串是否为回文bool isPalindrome(const string &s, int left, int right) {while (left < right) {if (s[left] != s[right]) return false;left++;right--;}return true;}// 回溯函数void backtrack(const string &s, int start, vector<string> &current_partition, vector<vector<string>> &result) {if (start == s.size()) {// 如果已经遍历完整个字符串，将当前划分加入结果result.push_back(current_partition);return;}for (int end = start; end < s.size(); ++end) {// 判断当前子串是否为回文if (isPalindrome(s, start, end)) {// 如果是回文，将其加入当前组合current_partition.push_back(s.substr(start, end - start + 1));// 继续递归处理剩余的字符串backtrack(s, end + 1, current_partition, result);// 回溯：移除最后一个加入的子串current_partition.pop_back();}}}
};

这篇关于代码随想录算法训练营第二十三天| 39. 组合总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！