加起来和为目标值的组合(二)

加起来和为目标值的组合(二)_牛客题霸_牛客网

问题简述

给出一组候选数 c 和一个目标数 t ，找出候选数中起来和等于 t 的所有组合。

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

注意：
1. 题目中所有的数字（包括目标数 t ）都是正整数
2. 组合中的数字要按非递减排序
3. 结果中不能包含重复的组合
4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

思路：DFS回溯

• 定义 dfs(start, rest) 表示从 start 开始遍历剩下的元素，剩余目标和 rest；

• 剪枝要点（详见代码）；

  • 先对 arr 排序；

  • 当前层跳过重复值，即 arr[i] == arr[i-1] 时 continue；

  • 遍历当前层元素时，若 rest < arr[i] 直接 break；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param num int整型一维数组 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def combinationSum2(self , arr: List[int], target: int) -> List[List[int]]:
        
        N = len(arr)
        arr.sort()
        ret = []
        tmp = []
        
        def dfs(start, rest):
            if rest == 0:
                ret.append(tmp[:])
                return
            
            for i in range(start, N):
                if i > start and arr[i] == arr[i - 1]:
                    continue
                # 因为排过序了，所以当前值不够的话，后面的肯定都不够了，直接全部剪掉
                if rest < arr[i]:
                    break
                    
                tmp.append(arr[i])
                # 注意这里不是 start + 1，而是 i + 1，表示下一层应该从 i + 1 开始尝试
                # dfs(start + 1, rest - arr[i])  # err
                dfs(i + 1, rest - arr[i])
                tmp.pop()
                    
        dfs(0, target)
        return ret