解题思路：

1. 回溯法：采用回溯算法来寻找所有符合条件的组合。每次选择一个候选数字，递归地减去这个数字，并继续选择，直到目标值 target 为 0。由于可以重复选择数字，因此递归过程中不会回退到前一个数字，而是从当前数字继续选择。

2. 递归过程：从数组中选择一个数字，如果该数字不大于当前目标值 target，就将其加入当前路径 path，并递归调用自己减少目标值。递归完成后，回溯时移除最后一个数字，继续尝试其他组合。

3. 终止条件：

   • 如果 target == 0，说明找到了一个符合条件的组合，加入结果中。
   • 如果 target < 0，说明当前路径不满足条件，返回。

4. 输入输出：输入包含目标和候选数组，输出每一行显示一个符合条件的组合。

代码实现：

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;
}

Leetcode 58.组合总和-原题链接

题目描述

给定一个无重复元素的整数数组 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