题解 | #加起来和为目标值的组合#

有重复数组，求和为target的combinations，先排序再去重

#
# 
# @param num int整型一维数组 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def combinationSum2(self , num , target ):
        # write code here
        def backtrack(num, target, curr, idx):
            curr_value = sum([num[i] for i in curr])
            if curr_value == target:
                self.res.append([num[i] for i in curr])
                return
            elif curr_value > target:
                return
            else:
                for i in range(idx, len(num)):
                    if i >= 1 and num[i] == num[i-1] and i-1 not in curr:
                        continue
                    curr.append(i)
                    backtrack(num, target, curr, i+1)
                    curr.pop()
        num.sort()
        self.res = []
        backtrack(num, target, [], 0)
        return self.res