#P4071. 组合总和
-
ID: 2312
Tried: 86
Accepted: 34
Difficulty: 4
组合总和
题目描述
给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为 target 的所有不同组合，并以任意顺序输出。
candidates 中的同一个数字可以被无限制重复选取。如果至少一个数字的被选数量不同，则两种组合视为不同组合。
保证不同组合的数量少于 150 个。
输入格式
- 第一行包含两个整数
n和target，分别表示数组的长度和目标值。 - 第二行包含
n个整数，表示数组candidates中的元素，元素互不相同。
输出格式
- 每一行输出一个组合，格式为若干个用空格分隔的整数，代表该组合中的元素。
- 输出的组合顺序不限，组合内的数字顺序也不限。
- 如果没有满足条件的组合，输出空行。
输入样例 1
4 7
2 3 6 7
输出样例 1
2 2 3
7
输入样例 2
3 8
2 3 5
输出样例 2
2 2 2 2
2 3 3
3 5
输入样例 3
1 1
2
输出样例 3
解题思路：
-
回溯法：采用回溯算法来寻找所有符合条件的组合。每次选择一个候选数字，递归地减去这个数字，并继续选择，直到目标值
target为 0。由于可以重复选择数字，因此递归过程中不会回退到前一个数字，而是从当前数字继续选择。 -
递归过程：从数组中选择一个数字，如果该数字不大于当前目标值
target，就将其加入当前路径path，并递归调用自己减少目标值。递归完成后，回溯时移除最后一个数字，继续尝试其他组合。 -
终止条件：
- 如果
target == 0，说明找到了一个符合条件的组合，加入结果中。 - 如果
target < 0，说明当前路径不满足条件，返回。
- 如果
-
输入输出：输入包含目标和候选数组，输出每一行显示一个符合条件的组合。
代码实现：
Java 代码：
import java.util.*;
public class Main {
// 回溯函数
public static void backtrack(int start, int target, int[] candidates, List<Integer> path, List<List<Integer>> res) {
if (target == 0) { // 如果目标为 0，说明找到一个组合，加入结果
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > target) continue; // 当前数字大于目标，跳过
path.add(candidates[i]);
backtrack(i, target - candidates[i], candidates, path, res); // 继续选择
path.remove(path.size() - 1); // 回溯，移除最后一个数字
}
}
// 主函数，调用回溯方法
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backtrack(0, target, candidates, path, res);
return res;
}
// 主函数，用于处理输入输出
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int target = scanner.nextInt();
int[] candidates = new int[n];
for (int i = 0; i < n; i++) {
candidates[i] = scanner.nextInt();
}
List<List<Integer>> result = combinationSum(candidates, target);
// 输出每个组合
for (List<Integer> combo : result) {
System.out.println(String.join(" ", combo.stream().map(String::valueOf).toArray(String[]::new)));
}
}
}
Python 代码：
def backtrack(start, target, candidates, path, res):
if target == 0: # 如果目标为 0，说明找到一个组合，加入结果
res.append(path)
return
for i in range(start, len(candidates)):
if candidates[i] > target: continue # 当前数字大于目标，跳过
backtrack(i, target - candidates[i], candidates, path + [candidates[i]], res) # 继续选择
def combinationSum(candidates, target):
res = []
backtrack(0, target, candidates, [], res)
return res
# 主程序
n, target = map(int, input().split()) # 输入 n 和 target
candidates = list(map(int, input().split())) # 输入 candidates 数组
result = combinationSum(candidates, target)
for combo in result:
print(" ".join(map(str, combo)))
C++ 代码：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void backtrack(int start, int target, vector<int>& candidates, vector<int>& path, vector<vector<int>>& res) {
if (target == 0) { // 如果目标为 0，说明找到一个组合，加入结果
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (candidates[i] > target) continue; // 当前数字大于目标，跳过
path.push_back(candidates[i]);
backtrack(i, target - candidates[i], candidates, path, res); // 继续选择
path.pop_back(); // 回溯，移除最后一个数字
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> path;
backtrack(0, target, candidates, path, res);
return res;
}
};
int main() {
int n, target;
cin >> n >> target;
vector<int> candidates(n);
for (int i = 0; i < n; i++) {
cin >> candidates[i];
}
Solution solution;
vector<vector<int>> result = solution.combinationSum(candidates, target);
for (auto& combo : result) {
for (int num : combo) {
cout << num << " ";
}
cout << endl;
}
return 0;
}