给定一个无重复元素的正整数数组 candidates 和一个正整数 target ,
找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同,则两种组合是唯一的。
对于给定的输入,保证和为 target 的唯一组合数少于 150 个。
示例 1:输入: candidates = [2,3,6,7], target = 7 输出: [[7],[2,2,3]]
示例 2:输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:输入: candidates = [2], target = 1 输出: []
示例 4:输入: candidates = [1], target = 1 输出: [[1]]
示例 5:输入: candidates = [1], target = 2 输出: [[1,1]]
提示:1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
注意:本题与主站 39 题相同:
1、递归;时间复杂度O(2^n),空间复杂度O(2^n)
var res [][]int
func combinationSum(candidates []int, target int) [][]int {
res = make([][]int, 0)
sort.Ints(candidates)
dfs(candidates, target, []int{}, 0)
return res
}
func dfs(candidates []int, target int, arr []int, index int) {
if target == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
if target < 0 {
return
}
for i := index; i < len(candidates); i++ {
arr = append(arr, candidates[i])
dfs(candidates, target-candidates[i], arr, i)
arr = arr[:len(arr)-1]
}
}
2、递归;时间复杂度O(2^n),空间复杂度O(2^n)
var res [][]int
func combinationSum(candidates []int, target int) [][]int {
res = make([][]int, 0)
sort.Ints(candidates)
dfs(candidates, target, []int{}, 0)
return res
}
func dfs(candidates []int, target int, arr []int, index int) {
if target == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := index; i < len(candidates); i++ {
if target < candidates[i] {
return
}
dfs(candidates, target-candidates[i], append(arr, candidates[i]), i)
}
}
Medium题目,题目同leetcode 39.组合总和
页面更新:2024-02-21
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号