LeetCode 39. 组合总和

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 39. 组合总和

思路分析

思路描述

参考代码

func combinationSum(candidates []int, target int) [][]int {
	res := make([][]int, 0)
	backtrack(candidates, target, []int{}, &res, 0)
	return res
}

func backtrack(candidates []int, target int, path []int, res *[][]int, start int) {
	if sum(path) == target {
		temp := make([]int, len(path))
		copy(temp, path)
		*res = append(*res, temp)
	} else if sum(path) > target {
		return
	}
	for i := start; i < len(candidates); i++ {
		path = append(path, candidates[i])
		backtrack(candidates, target, path, res, i)
		path = path[:len(path)-1]
	}
}

func sum(nums []int) int {
	total := 0
	for _, num := range nums {
		total += num
	}
	return total
}

🍏 点击查看 Java 题解

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, new ArrayList<>(), res, 0);
        return res;
    }

    public void backtrack(int[] candidates, int pathSum, List<Integer> path, List<List<Integer>> res, int start) {
        if (pathSum == 0) {
            res.add(new ArrayList<>(path));
            return;
        } else if (pathSum < 0) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtrack(candidates, pathSum - candidates[i], path, res, i);
            path.remove(path.size() - 1);
        }
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/47745585