组合总数
- 题目
- 题目描述
- 示例 1：
- 示例 2：
- 示例 3：
- 提示：
- 题解
- 解题思路
- python实现
- 代码解释
- 提交结果
题目
题目描述
给你一个 无重复元素 的整数数组 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
题解
解题思路
这个问题可以通过回溯算法（Backtracking）来解决。回溯是一种递归的搜索策略，它尝试构建所有可能的候选解，并在确定某个部分解不可能成为有效解时立即放弃这个部分解（即“回溯”）。对于这个问题，我们将尝试每个可能的数字组合，直到它们的和等于目标值target。
python实现
以下是Python代码实现：
def combinationSum(candidates, target):def backtrack(remain, combo, index):if remain == 0:# Make a deep copy of the current combinationresult.append(list(combo))returnelif remain < 0:# Exceeded the sum with the current combinationreturnfor i in range(index, len(candidates)):# Add the number into the combinationcombo.append(candidates[i])# Give the current number another chance, since we can reuse same elementsbacktrack(remain - candidates[i], combo, i)# Backtrack, remove the number from the combinationcombo.pop()result = []candidates.sort() # Sort candidates to help reduce unnecessary searchesbacktrack(target, [], 0)return result代码解释
这段代码中定义了一个名为backtrack的辅助函数，它接收剩余的目标值remain、当前的组合combo以及当前考虑的候选数组索引index作为参数。这个辅助函数将尝试从索引index开始的所有候选数，以构建出和为target的不同组合。
- 如果剩余的目标值
remain变为0，那么当前的组合就是一个有效的解，我们将其添加到结果列表中。 - 如果
remain小于0，那么说明当前的组合超出了目标值，因此我们停止进一步探索这个分支。 - 否则，我们遍历从
index到数组末尾的所有候选数，尝试将它们加入到当前组合中，并继续探索。 - 在每次递归调用之后，我们需要执行回溯操作，即将最后加入组合的那个数移除，以便尝试其他可能性。
此外，我们在开始回溯之前对candidates进行了排序，这有助于减少不必要的搜索路径，因为一旦我们发现某个候选数导致了超过目标值的结果，我们可以跳过后续更大的数。
提交结果
