40. 组合总和 II

题目描述

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

样例

Input：candidates = [10,1,2,7,6,1,5], target = 7,
Output：
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

题目解析

本题在 39. 组合总和 的基础上，放宽了非重复数字的约束条件。

根据之前的练习，可以知道，本题中我们需要解决两个问题。

一个是组合问题，参考 77. 组合(Medium)， 一个是重复问题 47. 全排列 II(Medium)

组合问题的关键是，使用 cur/startIndex 来标记每次循环的初始位置，使得每次递归的时候，只能向后找，不能向前找。

核心代码是

for i in range(cur, len(candidates)): # 从 cur 开始，可以避免走回头路
    ... 
    backtracking(candidates, target, i + 1, ans, tmp) # i + 1 向后找
    ...

重复问题的关键是 如何剪枝，根据 47. 全排列 II(Medium) 我们掌握了剪枝的核心方法是

num.sort()
if (num[i] == num[i - 1] and visited[i - 1] == False):
    continue # 跳过，剪枝

Python 代码示例

def backtracking(candidates, target, ans, cur, visited, tmp):
    if sum(tmp) == target:
        ans.append(tmp[:])
        return 
    elif sum(tmp) > target:
        return 
    
    for i in range(cur, len(candidates)):
        if i > 0 and candidates[i] == candidates[i - 1] and not visited[i - 1]: # 重复剪枝
            continue 
        visited[i] = 1
        tmp.append(candidates[i])
        backtracking(candidates, target, ans, i + 1, visited, tmp)
        tmp.pop()
        visited[i] = 0
    
    
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        visited = [0] * len(candidates)
        backtracking(candidates, target, ans, 0, visited, [])
        return ans 

Go 代码示例

func backtracking(candidates []int, visited []bool, startIndex int, ans *[][]int, tmp []int, target int) {
    if target == 0 {
        (*ans) = append((*ans), append([]int(nil), tmp...))
    } else if target < 0 {
        return 
    } 

    for i := startIndex; i < len(candidates); i++ {
        if i > 0 && candidates[i] == candidates[i - 1] && visited[i - 1] == false {
            continue
        }
        visited[i] = true
        tmp = append(tmp, candidates[i]) 
        backtracking(candidates, visited, i + 1, ans, tmp, target - candidates[i])
        tmp = tmp[:len(tmp) - 1]
        visited[i] = false
    }
}
func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    n := len(candidates)
    visited := make([]bool, n)
    ans := make([][]int, 0)
    backtracking(candidates, visited, 0, &ans, []int{}, target)
    return ans
}