# -*- coding: utf-8 -*-
# Given a set of candidate numbers (C) 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.
# Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
# 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 comsum(self, nums, target):
        i = 0
        result = []
        nums = sorted(nums)
        while i < len(nums):
            if target == nums[i]:
                result.append([nums[i]])
            elif target > nums[i]:
                temp = [nums[i]]
                num = target - nums[i]
                while num != 0 and num  > 0:
                    if num in nums and num > nums[i]:
                        temp.append(num)
                        result.append(temp)
                        break
                    else:
                        num = num - nums[i]
                        temp.append(nums[i])
            else:
                break
            i += 1
        return result

print Solution().comsum([2,3,4,6,7], 7)