Challenge: Make the Target

Lab Python Intermediate 20 points

Read some distinct positive numbers and a target. Print every combination (numbers may be reused) that adds up to the target, each in non-decreasing order, one per line with numbers separated by +. List them in the order backtracking finds them when the numbers are sorted. Then print Ways: <count>.

Input

Line 1: distinct positive whole numbers. Line 2: the target (at most 40).

Output

The combinations, then the count.

Example

Input

2 3 6 7
7

Output

2+2+3
7
Ways: 2

Sample input available Sample output available

Editor

Python

Hints

Sort the numbers first.

explore(start, left): try nums[start:] and pass i (not i + 1) so a number can repeat.

Stop the loop when nums[i] > left (pruning).

Solution explanation

Starting each loop at start keeps every combination in non-decreasing order, so none is printed twice.

Show solution

nums = sorted(map(int, input().split()))
target = int(input())
cur = []
ways = 0


def explore(start, left):
    global ways
    if left == 0:
        print("+".join(map(str, cur)))
        ways += 1
        return
    for i in range(start, len(nums)):
        if nums[i] > left:
            break
        cur.append(nums[i])
        explore(i, left - nums[i])
        cur.pop()


explore(0, target)
print("Ways:", ways)

Output

Answer