C++算法练习-day54——39.组合总和
题目来源：. - 力扣（LeetCode）
题目思路分析
题目：给定一个整数数组 candidates 和一个目标数 target，找出所有独特的组合，这些组合中的数字之和等于 target。每个数字在每个组合中只能使用一次。
思路：
-
回溯法：回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即“回溯”并尝试另一个可能的候选解。
-
剪枝：在回溯过程中，如果当前组合的和已经超过了目标值
target，则可以提前终止当前路径的搜索，因为后续添加任何数字都会使总和更大。（题目中已说明candidates中的数都大于1）
代码:
#include <vector> class Solution {
public: // 回溯函数 void Backtracking(vector<vector<int>>& ans, vector<int>& pos, vector<int>& candidates, int target, int index, int& possum) { // 如果当前组合的和超过了目标值，直接返回 if (possum > target) { return; } // 如果当前组合的和等于目标值，将当前组合加入结果集 if (possum == target) { ans.push_back(pos); } // 遍历候选数组，从当前索引开始（因为每个数字只能使用一次） for (; index < candidates.size(); ++index) { // 选择当前数字 possum += candidates[index]; pos.push_back(candidates[index]); // 递归调用回溯函数，继续向下搜索 Backtracking(ans, pos, candidates, target, index + 1, possum); // 撤销选择，回溯 possum -= candidates[index]; pos.pop_back(); } } // 主函数，调用回溯函数 vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<int> pos; // 当前组合 vector<vector<int>> ans; // 结果集 int possum = 0; // 当前组合的和 // 调用回溯函数，从索引0开始搜索 Backtracking(ans, pos, candidates, target, 0, possum); return ans; }
};知识点摘要
- 回溯法：一种通过递归和状态重置来构建所有可能解的算法。
- 剪枝：在搜索过程中提前终止不可能产生有效解的路径，以减少计算量。
- 状态重置：在回溯过程中，通过撤销选择来回到之前的状态，以便尝试其他可能的解。
通过这道题目，我们学习了如何使用回溯法来解决组合问题，并理解了剪枝和状态重置的重要性。回溯法是一种强大的算法，适用于解决许多组合和排列问题。在实际应用中，我们需要注意如何有效地进行剪枝，以减少不必要的计算，提高算法的效率。此外，对于涉及组合的问题，如果数组已排序，可以进一步简化问题，避免产生重复的组合。通过不断练习，我们可以更好地掌握回溯法的应用，提高解决复杂问题的能力。