C++算法练习-day54——39.组合总和

题目来源：. - 力扣（LeetCode）

题目思路分析

题目：给定一个整数数组 candidates 和一个目标数 target，找出所有独特的组合，这些组合中的数字之和等于 target。每个数字在每个组合中只能使用一次。

思路：

1. 回溯法：回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即“回溯”并尝试另一个可能的候选解。

2. 剪枝：在回溯过程中，如果当前组合的和已经超过了目标值 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;  }  
};

知识点摘要

1. 回溯法：一种通过递归和状态重置来构建所有可能解的算法。
2. 剪枝：在搜索过程中提前终止不可能产生有效解的路径，以减少计算量。
3. 状态重置：在回溯过程中，通过撤销选择来回到之前的状态，以便尝试其他可能的解。

通过这道题目，我们学习了如何使用回溯法来解决组合问题，并理解了剪枝和状态重置的重要性。回溯法是一种强大的算法，适用于解决许多组合和排列问题。在实际应用中，我们需要注意如何有效地进行剪枝，以减少不必要的计算，提高算法的效率。此外，对于涉及组合的问题，如果数组已排序，可以进一步简化问题，避免产生重复的组合。通过不断练习，我们可以更好地掌握回溯法的应用，提高解决复杂问题的能力。