def combination_sum(nums, target):
    # Initialize dp
    dp = [[] for _ in range(target + 1)]
    dp[0].append([])

    # For each value from 1 to target
    for i in range(1, target + 1):
        # Iterate over nums
        for j in range(len(nums)):
            if nums[j] <= i:

                # Check previous results from dp
                for prev in dp[i - nums[j]]:
                    temp = prev + [nums[j]]
                    temp.sort()
                    # If the new combination is not already in dp
                    if temp not in dp[i]:
                        dp[i].append(temp)
    # Return the combinations
    return dp[target]

# Driver code
def main():
    nums = [
            [2, 3, 5], 
            [3, 6, 7, 8], 
            [4, 5, 6, 9], 
            [20, 25, 30, 35, 40], 
            [3, 5, 7]
        ]

    targets = [5, 15, 11, 40, 15]

    for i in range(len(nums)):
            print(i+1, ".", "\tnums: ", nums[i], sep="")
            print("\tTarget: ", targets[i], sep="")
            combinations = combination_sum(nums[i], targets[i])
            print("\tNumber of Combinations: ", combinations, sep="")
            print("-" * 100)
            print()

if __name__ == '__main__':
    main()