30. All Subarrays With Sum K

Difficulty: medium · Array, Prefix Sum

Problem

You are given an array of integers followed by a target `K`, all on a single line: the array elements are separated by spaces, then a comma, then `K`. The size of the array is **not** given, so your program must read numbers until it reaches the comma. Print every contiguous subarray whose elements add up to exactly `K`. List them ordered by starting index, and subarrays with the same start by ending index. If no subarray has sum `K`, print `-1`.

Input

A single line: the array elements separated by single spaces, then a comma (`,`), then the integer `K`. There may be spaces on either side of the comma. Example: `1 2 3 4 5 -4 -3 ,10`

Output

Print each matching subarray on its own line with its elements separated by single spaces, or print `-1` if there are none.

Example 1

Input:
1 2 3 4 5 -4 -3 ,10
Output:
1 2 3 4
2 3 4 5 -4

Explanation: 1+2+3+4 = 10 (starting at index 0) and 2+3+4+5-4 = 10 (starting at index 1); no other contiguous run sums to 10.

Example 2

Input:
5 -5 5,0
Output:
5 -5
-5 5

Explanation: Both 5 -5 and -5 5 sum to 0; they are listed by starting index.

Example 3

Input:
1 2 3,100
Output:
-1

Explanation: No subarray reaches 100, so -1 is printed.

Constraints

- 1 <= number of elements <= 100 - -100 <= each element <= 100 - -10^4 <= K <= 10^4

Solutions are judged against 3 sample and 10 hidden tests. Sign in to solve it · All problems