leetcode39：组合总和

题目链接

leetcode

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    回溯，深度优先搜索 DFS

    时间复杂度：O(2^n)
        其中 n 是候选数字的数量。
        在最坏的情况下，每个数字都有两种选择：选择或不选择，因此总共有 2^n 种组合。
    空间复杂度：O(m)
        其中 m 是结果列表中元素的平均长度。
        在最坏的情况下，结果列表中的每个元素都包含所有 n 个数字，因此空间复杂度为 O(m)。
*/
class Solution_0 {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if (candidates.empty()) return res;
        dfs(candidates, target, 0);
        return res;
    }

    void dfs(vector<int>& candidates, int target, int start) {
         if (target == 0) {
            res.push_back(path);
            return;
        }
        if (start == candidates.size()) return;

        for (int i = start; i < candidates.size(); i ++) {
            if (candidates[i] <= target) {
                path.push_back(candidates[i]);
                dfs(candidates, target - candidates[i], i); // 一个数字可以被重复使用
                path.pop_back();
            }
        }
    }

private:
    vector<vector<int>> res;
    vector<int> path;
};

/*
    思路同上
	这道题的关键在于 candidates 中的元素可以重复使用。
*/
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if (candidates.empty()) return res;
        dfs(candidates, target, 0);
        return res;
    }

    void dfs(vector<int>& candidates, int target, int start) {
        // 找到目标和
        if (target == 0) {
            res.push_back(path);
            return;
        }
        // 超过目标和，直接结束
        if (target < 0) {
            return;
        }

        // 回溯算法框架
        for (int i = start; i < candidates.size(); i ++) {
            path.push_back(candidates[i]); // 选择
            target -= candidates[i];
            dfs(candidates, target, i);    // 递归遍历下一层回溯树
            target += candidates[i];       // 撤销选择
            path.pop_back();        
        }
    }

private:
    vector<vector<int>> res; // 结果数组
    vector<int> path;        // 记录回溯的路径
};

int main() {
    Solution solution;
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    vector<vector<int>> combinations = solution.combinationSum(candidates, target);
    cout << "Combinations that sum to " << target << " are:" << endl;
    for (const vector<int>& combination : combinations) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"sort"
)

/*
   回溯算法：
       使用回溯算法生成所有可能的组合，直到组合中的数字之和等于目标值。
       回溯算法通过递归模拟所有可能的选择路径，每次选择一个数字加入当前组合，并在递归返回时恢复状态。
   排序和剪枝：
       对 candidates 进行排序，方便在递归过程中进行剪枝。
       如果当前数字大于剩余目标值，则直接跳过，避免无效计算。
   重复使用数字：
       同一个数字可以无限制重复被选取，因此递归调用时传递的索引是当前索引 i，而不是 i+1。

    时间复杂度：O(2^n)
        其中 n 是候选数字的数量。
        在最坏的情况下，每个数字都有两种选择：选择或不选择，因此总共有 2^n 种组合。
    空间复杂度：O(m)
        其中 m 是结果列表中元素的平均长度。
        在最坏的情况下，结果列表中的每个元素都包含所有 n 个数字，因此空间复杂度为 O(m)。
*/
func combinationSum(candidates []int, target int) [][]int {
    // 对数组进行排序，方便剪枝
	sort.Ints(candidates)
    var result [][]int
    var path []int

    var dfs func(start int, remain int)
    dfs = func(start int, remain int) {
		// 如果剩余值为 0，说明找到了一个有效组合
        if remain == 0 {
			result = append(result, append([]int{}, path...))
            return
        }

		// 在剩余数字中选择
        for i := start; i < len(candidates); i ++ {
            // 如果当前数字大于剩余值，剪枝
            if candidates[i] > remain {
                break
            }
            // 选择当前数字
            path = append(path, candidates[i])
            // 递归调用，这里是 i 而不是 i+1，因为数字可以重复使用
            dfs(i, remain-candidates[i])
            // 撤销选择
            path = path[:len(path)-1]
        }
    }

	// 开始回溯
	dfs(0, target)
	return result
}

func main() {
	// 测试用例
	testCases := []struct {
		candidates []int
		target     int
		expected   [][]int
	}{
		{
			candidates: []int{2, 3, 6, 7},
			target:     7,
			expected:   [][]int{{2, 2, 3}, {7}},
		},
		{
			candidates: []int{2, 3, 5},
			target:     8,
			expected:   [][]int{{2, 2, 2, 2}, {2, 3, 3}, {3, 5}},
		},
		{
			candidates: []int{2},
			target:     1,
			expected:   [][]int{},
		},
	}

	for i, tc := range testCases {
		fmt.Printf("Test Case %d, Input: candidates = %v, target = %d\n", i+1, tc.candidates, tc.target)
		result := combinationSum(tc.candidates, tc.target)

		if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}