题目

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出:

[

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

示例 2:输入: candidates = [2,5,2,1,2], target = 5, 输出:

[

[1,2,2],

[5]

]

提示:1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

注意：本题与主站 40 题相同：

解题思路分析

1、递归；时间复杂度O(n!)，空间复杂度O(n!)

var res [][]int

func combinationSum2(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++ {
		origin := i
		for i < len(candidates)-1 && candidates[i] == candidates[i+1] {
			i++
		}
		arr = append(arr, candidates[i])
		dfs(candidates, target-candidates[i], arr, origin+1)
		arr = arr[:len(arr)-1]
	}
}

2、递归；时间复杂度O(n!)，空间复杂度O(n!)

var res [][]int

func combinationSum2(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 i != index && candidates[i] == candidates[i-1] {
         continue
      }
      if target < 0 {
         return
      }
      arr = append(arr, candidates[i])
      dfs(candidates, target-candidates[i], arr, i+1)
      arr = arr[:len(arr)-1]
   }
}

总结

Medium题目，题目同leetcode 40.组合总和II