leetcode-39 组合总和

留言

相关:

leetcode-46 全排列
leetcode-47 全排列 II

leetcode-39 组合总和
leetcode-40 组合总和 II


&此题为使用 回溯 进行求解的典型 &

（递归&回溯）

39. 组合总和

难度: 中等

需要用到DFS(深度优先搜索)

[Golang-Leetcode]组合总和-解题思路

Leetcode No.39 组合总和（DFS）

LeetCode 39. 组合总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main

import "sort"

func combinationSum(candidates []int, target int) [][]int {
	if len(candidates) == 0 {
		return [][]int{}
	}
	c, res := []int{}, [][]int{}
	sort.Ints(candidates)
	findcombinationSum(candidates, target, 0, c, &res)
	return res
}

func findcombinationSum(nums []int, target, index int, c []int, res *[][]int) {
	if target <= 0 {
		if target == 0 {
			b := make([]int, len(c))
			copy(b, c)
			*res = append(*res, b)
		}
		return
	}
	for i := index; i < len(nums); i++ {
		if nums[i] > target { // 这里可以剪枝优化
			break
		}
		c = append(c, nums[i])
		findcombinationSum(nums, target-nums[i], i, c, res) // 注意这里迭代的时候 index 依旧不变，因为一个元素可以取多次
		c = c[:len(c)-1]
	}
}

文章目录