leetcode: 39. Combination Sum

# coding=utf-8

# Given a set of candidate numbers (C) (without duplicates) and a target number (T),
# find all unique combinations in C where the candidate numbers sums to T.
#
# The same repeated number may be chosen from C unlimited number of times.
#
# Note:
#
# All numbers (including target) will be positive integers.
# The solution set must not contain duplicate combinations.
#
# For example, given candidate set [2, 3, 6, 7] and target 7, 
# A solution set is: 
#
# [
#   [7],
#   [2, 2, 3]
# ]

class Solution():
    def combinationSum(self, x, target):
        x.sort()
        res = []
        self.dfs(res, x, target-0, 0, [])
        return res
    def dfs(self, res, x, diff, start, path):
        if diff == 0:   # 加上 path not in res 可去重
            res.append(path)
        elif diff > 0:
            for j in range(start, len(x)):
                # 改为 self.dfs(res, x, diff-x[j], j+1, path+[x[j]]) 则 子数组 内 不含有 下标相同的元素
                self.dfs(res, x, diff-x[j], j, path+[x[j]])


if __name__ == "__main__":
    assert Solution().combinationSum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]