Сумма

면접 대비

시간 제한1초메모리 제한1024 MB

요약

합이 n이고 이웃한 항의 차가 1 이하인 정수 k개짜리 순서 있는 표현을 모두 사전순으로 출력한다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 백트래킹, 재귀
정답자: 아직 제출이 없습니다

문제

Даша очень любит представлять числа в виде суммы. Сегодня Даша хочет выписать все возможные представления числа $n$ в виде суммы $k$ слагаемых.

При этом она не любит, когда слагаемые меняются слишком быстро. А именно, соседние слагаемые в представлении Даши должны различаться не больше, чем на единицу. Она использует и положительные, и отрицательные, и даже нулевые слагаемые, порядок слагаемых важен.

Выведите все представления, которые подходят по Дашины ограничения. Разбиения следует упорядочить по первому слагаемому, при равном первом слагаемом --- по второму, при равных первых двух --- по третьему, и так далее.

입력

Первая строка ввода содержит число $n$ ( $-15\le n \le 15$ ).

Вторая строка содержит число $k$ ( $1 \le k \le 15$ ).

Гарантируется, что общее число представлений не превышает $10^5$ .

출력

Выводите представления по одному на строке, перед положительными и нулевыми слагаемыми, кроме первого в представлении, выводите знак плюс. Не выводите пробелы.

예제1

예제 1

입력

2
4

예상 출력

-1+0+1+2
0+0+1+1
0+1+0+1
0+1+1+0
1+0+0+1
1+0+1+0
1+1+0+0
2+1+0-1