题目
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 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
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]
}
}