0039. Combination Sum

# 39. Combination Sum#

## 题目 #

Given a set of candidate numbers (`candidates`(without duplicates) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

The same repeated number may be chosen from `candidates` unlimited number of times.

Note:

• All numbers (including `target`) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

``````Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
``````

Example 2:

``````Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
``````

## 题目大意 #

candidates 中的数字可以无限制重复被选取。

## 解题思路 #

• 题目要求出总和为 sum 的所有组合，组合需要去重。
• 这一题和第 47 题类似，只不过元素可以反复使用。

## 代码 #

``````
package leetcode

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

``````

Apr 8, 2023