c++-c++编程基础之leetcode题解第39题组合总和.zip资源-CSDN文库

共1个文件

md：1个

需积分: 1 180 浏览量 2024-04-08 05:30:44 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第39题"组合总和"（Combination Sum）是LeetCode中的一道经典问题，它涉及到数组操作、回溯算法以及组合问题的解决策略。题目描述：给定一个无重复元素的整数数组`candidates`和一个目标整数`target`，找出`candidates`中的所有可以使数字和为`target`的组合。你可以假设每个输入都只对应一种答案，且同样的元素不能被重复利用。例如，给定`candidates = [2, 3, 6, 7]`和`target = 7`，因为`2 + 3 = 5`，`2 + 5 = 7`，所以返回`[[2, 5], [7]]`。解题思路：这道题目可以通过回溯算法来解决。回溯算法是一种试探性的解决问题的方法，它尝试分步地生成所有可能的解决方案，并在过程中剪枝（即剔除不可能的情况），以避免生成无效或重复的解。 1. 定义一个递归函数，接收当前的组合、剩余的元素、目标值以及当前选择的元素索引。 2. 当目标值为0时，说明找到了一个有效的组合，将其添加到结果列表中。 3. 在每次递归调用中，遍历当前元素索引到数组末尾的所有元素，将它们添加到当前组合，并尝试递归解决剩余的子问题。 4. 如果当前元素加上剩余目标值大于目标值，那么这个选择会导致组合和超过目标，可以剪枝，直接返回。 5. 否则，继续尝试下一个更大的元素，直到尝试完所有可能的元素。 6. 在递归返回后，移除最后加入的元素，回溯到上一步，尝试其他的元素组合。 C++代码实现如下： ```cpp vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> current; backtrack(candidates, target, result, current, 0); return result; } void backtrack(vector<int>& candidates, int target, vector<vector<int>>& result, vector<int>& current, int start) { if (target == 0) { result.push_back(current); return; } if (target < 0) { return; } for (int i = start; i < candidates.size(); i++) { current.push_back(candidates[i]); backtrack(candidates, target - candidates[i], result, current, i); // 不要回溯到已经选择过的元素 current.pop_back(); } } ``` 在这段代码中，`combinationSum`函数是主函数，`backtrack`是递归函数。注意，回溯时为了避免重复的解，我们从`start`位置开始选择元素，而不是从头开始，这样可以确保不选择同一个元素多次。总结：通过解决LeetCode的第39题"组合总和"，我们可以学习到C++中如何运用回溯算法解决组合问题，同时加深对数组操作、递归以及剪枝策略的理解。这样的练习对于提升C++编程能力，尤其是算法思维，是非常有帮助的。在实际编程中，类似的问题可能出现在各种场景，如组合优化、路径搜索等，掌握这种算法能够为解决复杂问题打下坚实的基础。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第39题组合总和.zip （1个子文件）

c++_c++编程基础之leetcode题解第39题组合总和

README.md 5KB

# [39. Combination Sum (Medium)](https://leetcode.com/problems/combination-sum/) Given an array of distinct integers <code>candidates</code> and a target integer <code>target</code>, return a list of all unique combinations of <code>candidates</code> where the chosen numbers sum to <code>target</code>. You may return the combinations in any order. The same number may be chosen from <code>candidates</code> an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. It is guaranteed that the number of unique combinations that sum up to <code>target</code> is less than <code>150</code> combinations for the given input.   Example 1: <pre>Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations. </pre> Example 2: <pre>Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] </pre> Example 3: <pre>Input: candidates = [2], target = 1 Output: [] </pre>   Constraints: <ul> <li><code>1 <= candidates.length <= 30</code></li> <li><code>1 <= candidates[i] <= 200</code></li> <li>All elements of <code>candidates</code> are distinct.</li> <li><code>1 <= target <= 500</code></li> </ul> **Companies**: [Facebook](https://leetcode.com/company/facebook), [Amazon](https://leetcode.com/company/amazon), [Airbnb](https://leetcode.com/company/airbnb), [Microsoft](https://leetcode.com/company/microsoft), [Apple](https://leetcode.com/company/apple), [Snapchat](https://leetcode.com/company/snapchat), [Adobe](https://leetcode.com/company/adobe), [Goldman Sachs](https://leetcode.com/company/goldman-sachs), [Salesforce](https://leetcode.com/company/salesforce) **Related Topics**: [Array](https://leetcode.com/tag/array/), [Backtracking](https://leetcode.com/tag/backtracking/) **Similar Questions**: * [Letter Combinations of a Phone Number (Medium)](https://leetcode.com/problems/letter-combinations-of-a-phone-number/) * [Combination Sum II (Medium)](https://leetcode.com/problems/combination-sum-ii/) * [Combinations (Medium)](https://leetcode.com/problems/combinations/) * [Combination Sum III (Medium)](https://leetcode.com/problems/combination-sum-iii/) * [Factor Combinations (Medium)](https://leetcode.com/problems/factor-combinations/) * [Combination Sum IV (Medium)](https://leetcode.com/problems/combination-sum-iv/) ## Solution 1. Backtracking ```cpp // OJ: https://leetcode.com/problems/combination-sum // Author: github.com/lzl124631x // Time: O(N^(T/M+1)) where N is the length of A, T is target and M is the minimum value of A[i] // Space: O(T/M) class Solution { public: vector<vector<int>> combinationSum(vector<int>& A, int target) { vector<vector<int>> ans; vector<int> tmp; function<void(int, int)> dfs = [&](int i, int target) { if (target == 0) { ans.push_back(tmp); return; } if (i == A.size()) return; int cnt = 0; do { dfs(i + 1, target); tmp.push_back(A[i]); target -= A[i]; ++cnt; } while (target >= 0); while (cnt-- > 0) tmp.pop_back(); }; dfs(0, target); return ans; } }; ``` ## Solution 2. Backtracking ```cpp // OJ: https://leetcode.com/problems/combination-sum // Author: github.com/lzl124631x // Time: O(N^(T/M+1)) where N is the length of A, T is target and M is the minimum value of A[i] // Space: O(T/M) class Solution { public: vector<vector<int>> combinationSum(vector<int>& A, int target) { vector<vector<int>> ans; vector<int> tmp; function<void(int, int)> dfs = [&](int start, int target) { if (target == 0) { ans.push_back(tmp); } else if (target < 0) return; for (int i = start; i < A.size(); ++i) { tmp.push_back(A[i]); dfs(i, target - A[i]); tmp.pop_back(); } }; dfs(0, target); return ans; } }; ``` Or ```cpp // OJ: https://leetcode.com/problems/combination-sum/ // Author: github.com/lzl124631x // Time: O(N^(T/M+1)) where N is the length of A, T is target and M is the minimum value of A[i] // Space: O(T/M) // Ref: https://discuss.leetcode.com/topic/14654/accepted-16ms-c-solution-use-backtracking-easy-understand class Solution { public: vector<vector<int>> combinationSum(vector<int>& A, int target) { vector<vector<int>> ans; vector<int> tmp; sort(begin(A), end(A)); // sorting is a must for this algorithm function<void(int, int)> dfs = [&](int start, int target) { if (target == 0) { ans.push_back(tmp); } for (int i = start; i < A.size() && target - A[i] >= 0; ++i) { tmp.push_back(A[i]); dfs(i, target - A[i]); tmp.pop_back(); } }; dfs(0, target); return ans; } }; ```

评论收藏

内容反馈