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

'''
解题思路：
1、使用DFS+回溯求解组合问题，dfs(iStart,res)，其中iStart为搜索起点，res保存搜索路径，
2、持续搜索约束条件为当前路径和 num[i]+s 小于等于80，达到目标值时保存搜索路径
3、先排序，组合搜索范围 for i in range(iStart,n)，利用i>iStart and num[i]==num[i-1]条件，去除重复搜索（i-1的搜索结果，必然包含i的结果）
4、dfs(i+1,res+[num[i]]) ，采用 res+[num[i]] 传参数自动回溯
'''
# @param num int整型一维数组 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def combinationSum2(self , num , target ):
        # write code here

        n = len(num)        
        num = sorted(num)        
        #print(num)

        iStart = 0        
        res = []
        out = []     
        def dfs(iStart,res):            
            s = sum(res)                    # 路径和

            if s>target:
                return

            if s==target:
                if res not in out:          # 这里也可以去重
                    out.append(res)         # 保存路径
                return                      # 返回空回溯

            for i in range(iStart,n):
                dfs(i+1,res+[num[i]])       # i+1,增加路径

        dfs(iStart,res)
        #print(out)
        return out

#Solution().combinationSum2([100,10,20,70,60,10,50],80)  # [[10,10,60],[10,20,50],[10,70],[20,60]]

'''        
        def dfs(iStart,res):

            s = sum(res)                    # 路径和
            if s==target:
                if res not in out:          # 这里也可以去重
                    out.append(res)         # 保存路径
                return                      # 返回空回溯

            for i in range(iStart,n):
                if i>iStart and num[i]==num[i-1]:  # 去除重复搜索（i-1的搜索结果，必然包含i的结果）
                    continue
                if num[i]+s <= target:             # 持续搜索约束条件为当前路径和 num[i]+s 小于等于80          
                    dfs(i+1,res+[num[i]])          # i+1,增加路径
'''