组合总和

题目要求

你需要编写一个算法，该算法的输入是一个不包含重复元素的整数数组 candidates 和一个目标整数 target。你的任务是找出所有不同的组合，这些组合中的数字加起来等于 target。结果应以列表的形式返回，列表中的每个元素是一个可能的组合，且组合内的数字可以是 candidates 中的任意数字重复多次。需要注意的是，组合中数字的顺序不影响组合的唯一性，即 [2,2,3] 和 [2,3,2] 视为同一组合。

解题思路

这个问题可以通过回溯算法来解决。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个有效的解，或者不可能产生一个有效的解，那么这个算法会回溯到上一步，然后通过改变上一步的解继续尝试找出有效的解。

解题步骤如下：

1. 排序（可选）：首先，可以对数组 candidates 进行排序。这一步不是必须的，但有时可以帮助更快地剪枝，尤其是当目标数 target 较小，而 candidates 中的数较大时。

2. 定义回溯函数：定义一个回溯函数，该函数将递归地尝试所有可能的组合方式。这个函数可以接受参数，如当前组合 combination，当前组合的和 current_sum，以及当前考虑的 candidates 的起始位置 start_index。

3. 递归与回溯：从 start_index 开始，遍历 candidates 数组。对于每个数，你可以选择“使用”或“不使用”它：

   • 如果当前组合的和加上这个数小于或等于 target，则“使用”这个数，将其添加到当前组合中，并递归调用回溯函数，同时 current_sum 加上这个数，start_index 保持不变（因为可以重复使用）。
   • 如果当前组合的和加上这个数大于 target，则“不使用”这个数，并停止遍历更大的数，因为数组是排序过的，更大的数只会使和更大。
   • 每次从回溯函数返回时，需要将最后一个添加到组合中的数移除，以便尝试其他可能的数。

4. 终止条件：如果当前组合的和等于 target，则将其添加到结果列表中。如果 current_sum 大于 target 或者没有更多的数可以添加，回溯。

5. 去重：由于结果要求是不同的组合，需要确保不会添加重复的组合。由于我们从 start_index 开始，并且每次递归时都不减少 start_index，所以同一层递归中不会有重复的组合。

6. 初始化和调用：最后，初始化一个空的结果列表，调用回溯函数，并传入初始参数。

通过以上步骤，你可以找到所有和为 target 的组合。

Golang 版本

package main

import "sort"

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates) // 可选的排序步骤
    var res [][]int
    var temp []int

    // 定义回溯函数
    var backtrack func(start int, target int)
    backtrack = func(start int, target int) {
        // 终止条件
        if target == 0 {
            // 添加当前组合的副本（因为temp后面会变）
            res = append(res, append([]int(nil), temp...))
            return
        }

        for i := start; i < len(candidates); i++ {
            // 如果当前数大于target，则后面的数也不用尝试了
            if candidates[i] > target {
                break
            }
            // 选择当前数
            temp = append(temp, candidates[i])
            // 递归调用，由于可以重复使用，start仍然是i
            backtrack(i, target-candidates[i])
            // 撤销选择
            temp = temp[:len(temp)-1]
        }
    }

    // 调用回溯函数
    backtrack(0, target)
    return res
}

func main() {
    // 示例
    candidates := []int{2, 3, 6, 7}
    target := 7
    combinations := combinationSum(candidates, target)
    // 输出结果
    fmt.Println(combinations)
}

这段代码定义了一个 combinationSum 函数，它接受一个整数数组 candidates 和一个目标整数 target，返回一个二维整数数组，其中包含所有加和为 target 的组合。在 main 函数中，我们给出了一个示例输入，并调用 combinationSum 函数，然后打印出结果。

C++版本

#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    void backtrack(std::vector<int>& candidates, int target, std::vector<std::vector<int>>& res, std::vector<int>& combination, int start) {
        if (target == 0) {
            res.push_back(combination);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > target) // 如果当前数大于target，则后面的数也不用尝试了
                break;

            combination.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], res, combination, i); // 因为可以重复使用，所以传入的是i而不是i+1
            combination.pop_back(); // 撤销选择
        }
    }

    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> res;
        std::vector<int> combination;
        std::sort(candidates.begin(), candidates.end()); // 可选的排序步骤
        backtrack(candidates, target, res, combination, 0);
        return res;
    }
};

int main() {
    Solution solution;
    std::vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    std::vector<std::vector<int>> combinations = solution.combinationSum(candidates, target);

    // 打印结果
    for (const auto& combination : combinations) {
        std::cout << '[';
        for (int i = 0; i < combination.size(); ++i) {
            std::cout << combination[i];
            if (i < combination.size() - 1) std::cout << ", ";
        }
        std::cout << ']' << std::endl;
    }

    return 0;
}

这段代码定义了一个 Solution 类，其中包含了 combinationSum 方法，用于找出所有和为 target 的组合。backtrack 是一个递归函数，用于执行回溯算法。在 main 函数中，我们创建了一个 Solution 对象，并给出了一个示例输入，然后调用 combinationSum 方法，并打印出结果。

Python 版本

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start: int, target: int, path: List[int]):
            if target == 0:
                res.append(path)
                return
            for i in range(start, len(candidates)):
                if candidates[i] > target:
                    break
                backtrack(i, target - candidates[i], path + [candidates[i]])

        candidates.sort()  # 可选的排序步骤
        res = []
        backtrack(0, target, [])
        return res

# 示例
if __name__ == '__main__':
    candidates = [2, 3, 6, 7]
    target = 7
    solution = Solution()
    combinations = solution.combinationSum(candidates, target)
    print(combinations)

这段代码定义了一个 Solution 类，其中包含了 combinationSum 方法，用于找出所有和为 target 的组合。backtrack 是一个内部函数，用于执行回溯算法。在 if __name__ == '__main__': 部分，我们给出了一个示例输入，然后调用 combinationSum 方法，并打印出结果。

Java 版本

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // 可选的排序步骤
        List<List<Integer>> results = new ArrayList<>();
        backtrack(candidates, target, results, new ArrayList<>(), 0);
        return results;
    }

    private void backtrack(int[] candidates, int target, List<List<Integer>> results, List<Integer> current, int start) {
        if (target == 0) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break;
            }
            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], results, current, i); // 因为可以重复使用，所以传入的是i而不是i+1
            current.remove(current.size() - 1); // 撤销选择
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> combinations = solution.combinationSum(candidates, target);
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}

这段代码定义了一个 Solution 类，其中包含了 combinationSum 方法，用于找出所有和为 target 的组合。backtrack 是一个私有辅助方法，用于执行回溯算法。在 main 方法中，我们创建了一个 Solution 对象，并给出了一个示例输入，然后调用 combinationSum 方法，并打印出结果。

Rust 版本

use std::vec::Vec;

fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    let mut combination = Vec::new();
    backtrack(&candidates, target, &mut results, &mut combination, 0);
    results
}

fn backtrack(
    candidates: &Vec<i32>,
    target: i32,
    results: &mut Vec<Vec<i32>>,
    combination: &mut Vec<i32>,
    start: usize,
) {
    if target == 0 {
        results.push(combination.clone());
        return;
    }

    for i in start..candidates.len() {
        if candidates[i] > target {
            break; // Prune the recursion tree
        }
        combination.push(candidates[i]);
        backtrack(candidates, target - candidates[i], results, combination, i); // Not i + 1 because we can reuse same elements
        combination.pop(); // Remove last element before moving to next
    }
}

fn main() {
    let candidates = vec![2, 3, 6, 7];
    let target = 7;
    let combinations = combination_sum(candidates, target);
    for combination in combinations {
        println!("{:?}", combination);
    }
}

这段代码定义了一个 combination_sum 函数，它接受一个整数向量 candidates 和一个目标整数 target，返回一个二维整数向量，其中包含所有加和为 target 的组合。backtrack 是一个辅助函数，用于执行回溯算法。在 main 函数中，我们给出了一个示例输入，并调用 combination_sum 函数，然后打印出结果。

总结

上述解法采用了回溯算法来解决组合总和问题。这个问题要求找出所有可能的组合，这些组合中的数字来自于一个候选数组，且它们的和等于一个目标值。在这些组合中，每个数字可以重复使用多次。

解法的关键步骤如下：

1. 排序（可选）：首先对候选数组进行排序，这样可以在回溯过程中更快地剪枝，因为一旦当前的数字加和已经超过目标值，就可以停止尝试更大的数字。

2. 回溯函数：定义一个回溯函数 backtrack，它将递归地尝试所有可能的组合。这个函数接受当前的组合 combination，当前的目标值 target，以及当前考虑的候选数字的起始索引 start。

3. 递归终止条件：如果当前的目标值减到了 0，说明找到了一个有效的组合，将其添加到结果集中。

4. 循环和递归：从 start 索引开始，遍历候选数组。对于每个数字，如果它不大于当前的目标值，就将它添加到当前组合中，并递归调用 backtrack 函数，此时目标值减去当前数字的值，start 索引不变。

5. 回溯：在每次递归调用之后，需要将最后一个加入到当前组合中的数字移除，这样才能回到之前的状态，尝试其他可能的数字。

6. 结果返回：所有递归完成后，返回结果集，它包含了所有可能的组合。

这种解法在不同的编程语言中都可以实现，上面提供了 C++, Java, Python 和 Rust 版本的代码实现。每种语言的实现都遵循了相同的逻辑结构，只是在语法和一些数据结构的使用上有所不同。