📑 题目：40. 组合总和 II

🚀 本题 LeetCode 传送门

题目大意

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

candidates 中的每个数字在每个组合中只能使用一次。

解题思路

  • 题目要求出总和为 sum 的所有组合，组合需要去重。这一题是第 39 题的加强版，第 39 题中元素可以重复利用(重复元素可无限次使用)，这一题中元素只能有限次数的利用，因为存在重复元素，并且每个元素只能用一次(重复元素只能使用有限次)
  • 这一题和第 47 题类似，只不过元素可以反复使用。

代码

  1. package leetcode
  3. import (
  4.  ""sort""
  5. )
  7. func combinationSum2(candidates []int, target int) [][]int {
  8.  if len(candidates) == 0 {
  9.   return [][]int{}
  10.  }
  11.  c, res := []int{}, [][]int{}
  12.  sort.Ints(candidates) // 这里是去重的关键逻辑
  13.  findcombinationSum2(candidates, target, 0, c, &res)
  14.  return res
  15. }
  17. func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) {
  18.  if target == 0 {
  19.   b := make([]int, len(c))
  20.   copy(b, c)
  21.   *res = append(*res, b)
  22.   return
  23.  }
  24.  for i := index; i < len(nums); i++ {
  25.   if i > index && nums[i] == nums[i-1] { // 这里是去重的关键逻辑,本次不取重复数字，下次循环可能会取重复数字
  26.    continue
  27.   }
  28.   if target >= nums[i] {
  29.    c = append(c, nums[i])
  30.    findcombinationSum2(nums, target-nums[i], i+1, c, res)
  31.    c = c[:len(c)-1]
  32.   }
  33.  }
  34. }