【综合算法学习】（第十篇）
目录
⽬标和（medium）
题目解析
讲解算法原理
编写代码
组合总和（medium）
题目解析
讲解算法原理
编写代码
⽬标和（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组nums和⼀个整数target。
向数组中的每个整数前添加'+'或'-'，然后串联起所有整数，可以构造⼀个表达式：例如，nums=[2,1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"
。
返回可以通过上述⽅法构造的、运算结果等于target的不同表达式的数⽬。
• ⽰例1：
输⼊：nums=[1,1,1,1,1],target=3
输出：5
解释：
⼀共有5种⽅法让最终⽬标和为3。
-1+1+1+1+1=3
+1-1+1+1+1=3
+1+1-1+1+1=3
+1+1+1-1+1=3
+1+1+1+1-1=3
• ⽰例2：
输⼊：nums=[1],target=1
输出：1
讲解算法原理
解法（回溯）：
算法思路：
对于每个数，可以选择加上或减去它，依次枚举每⼀个数字，在每个数都被选择时检查得到的和是否等于⽬标值。如果等于，则记录结果。
需要注意的是，为了优化时间复杂度，可以提前计算出数组中所有数字的和sum，以及数组的⻓度len。这样可以快速判断当前的和减去剩余的所有数是否已经超过了⽬标值target，或者当前的和加上剩下的数的和是否⼩于⽬标值target，如果满⾜条件，则可以直接回溯。
递归流程：
1. 递归结束条件：index与数组⻓度相等，判断当前状态的sum是否与⽬标值相等，若是计数加⼀；
2. 选择当前元素进⾏加操作，递归下⼀个位置，并更新参数sum；
3. 选择当前元素进⾏减操作，递归下⼀个位置，并更新参数sum；
• 特别地，此问题可以转化为另⼀个问题：若所有元素初始状态均为减，选择其中⼏个元素将他们的状态修改为加，计算修改后的元素和与⽬标值相等的⽅案个数。
1. 选择其中x个元素进⾏修改，并且这x个元素的和为y；
2. 检查使得-sum+2*y=target（移项：y=(sum+target)/2）成⽴的⽅案个数，即选择x个元素和为
(sum+target)/2的⽅案个数；
a. 若sum+target为奇数，则不存在这种⽅案；
3. 递归流程：
a. 传⼊参数：index（当前要处理的元素下标），sum（当前状态和），nums（元素数组），
aim（⽬标值：(sum+target)/2）；
b. 递归结束条件：index与数组⻓度相等，判断当前sum是否与⽬标值相等，若是返回1，否则
返回0；
c. 返回递归选择当前元素以及递归不选择当前元素函数值的和。
编写代码
c++算法代码：
class Solution
{
int ret, aim;
public:
int findTargetSumWays(vector<int>& nums, int target)
{
aim = target;
dfs(nums, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int path)
{
if(pos == nums.size())
{
if(path == aim) ret++;
return;
}
// 加法
dfs(nums, pos + 1, path + nums[pos]);
// 减法
dfs(nums, pos + 1, path - nums[pos]);
}
};java算法代码：
class Solution
{
int ret, aim;
public int findTargetSumWays(int[] nums, int target)
{
aim = target;
dfs(nums, 0, 0);
return ret;
}
public void dfs(int[] nums, int pos, int path)
{
if(pos == nums.length)
{
if(path == aim) ret++;
return;
}
// 加法
dfs(nums, pos + 1, path + nums[pos]);
// 减法
dfs(nums, pos + 1, path - nums[pos]);
}
}组合总和（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个⽆重复元素的整数数组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
讲解算法原理
解法：算法思路：
candidates的所有元素互不相同，因此我们在递归状态时只需要对每个元素进⾏如下判断：
1. 跳过，对下⼀个元素进⾏判断；
2. 将其添加⾄当前状态中，我们在选择添加当前元素时，之后仍可以继续选择当前元素（可以重复选择同⼀元素）。• 因此，我们在选择当前元素并向下传递下标时，应该直接传递当前元素下标。
递归函数设计：voiddfs(vector<int>&candidates,inttarget,vector<vector<int>>&ans,vector<int>&combine,intidx)
参数：target（当前状态和与⽬标值的差），idx（当前需要处理的元素下标）；返回值：⽆；
函数作⽤：向下传递两个状态（跳过或者选择当前元素），找出所有组合使得元素和为⽬标值。
递归函数流程如下：
1. 结束条件：
a. 当前需要处理的元素下标越界；b. 当前状态的元素和已经与⽬标值相同；
2. 跳过当前元素，当前状态不变，对下⼀个元素进⾏处理；
3. 选择将当前元素添加⾄当前状态，并保留状态继续对当前元素进⾏处理，递归结束时撤销添加操
作。
编写代码
c++算法代码：
class Solution
{
int aim;
vector<int> path;
vector<vector<int>> ret;
public:
vector<vector<int>> combinationSum(vector<int>& nums, int target)
{
aim = target;
dfs(nums, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int sum)
{
if(sum == aim)
{
ret.push_back(path);
return;
}
if(sum > aim || pos == nums.size()) return;
// 枚举个数
for(int k = 0; k * nums[pos] + sum <= aim; k++)
{
if(k) path.push_back(nums[pos]);
dfs(nums, pos + 1, sum + k * nums[pos]);
}
// 恢复现场
for(int k = 1; k * nums[pos] + sum <= aim; k++)
{
path.pop_back();
}
}
};Java算法代码：
class Solution
{
int aim;
List<Integer> path;
List<List<Integer>> ret;
public List<List<Integer>> combinationSum(int[] nums, int target)
{
path = new ArrayList<>();
ret = new ArrayList<>();
aim = target;
dfs(nums, 0, 0);
return ret;
}
public void dfs(int[] nums, int pos, int sum)
{
if(sum == aim)
{
ret.add(new ArrayList<>(path));
return;
}
if(sum > aim || pos == nums.length) return;
// 枚举 nums[pos] 使⽤多少个
for(int k = 0; k * nums[pos] + sum <= aim; k++)
{
if(k != 0) path.add(nums[pos]);
dfs(nums, pos + 1, sum + k * nums[pos]);
}
// 恢复现场
for(int k = 1; k * nums[pos] + sum <= aim; k++)
{
path.remove(path.size() - 1);
}
}
}