dp-jose.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int dp[1 << N];
int sum[1 << N];
int n, k, p[N], target;

int f(int mask) {
	if(mask == (1 << n) - 1) return 0;

	int &ans = dp[mask];
	if(~ans) return ans;

	ans = 0;

	for(int i = 0; i < n; i++) {
		if(!(mask >> i & 1)) {
			int nmask = mask ^ (1 << i);
			ans = max(ans, f(nmask) + !(sum[nmask] % target));
		}
	}
	return ans;
}

int main() {
	memset(dp, -1, sizeof dp);

	scanf("%d %d", &n, &k);

	for(int i = 0; i < n; i++) scanf("%d", p + i);

	for(int mask = 1; mask < (1 << n); mask++) {
		int bit = 31 - __builtin_clz(mask & -mask);
		sum[mask] = sum[mask ^ (1 << bit)] + p[bit];
	}

	if(sum[(1 << n) - 1] % k) return printf("impossivel\n"), 0;

	target = sum[(1 << n) - 1] / k;

	if(f(0) != k) return printf("impossivel\n"), 0;

	vector<int> ans;
	int mask = 0;
	while(mask < (1 << n) - 1) {
		for(int i = 0; i < n; i++) {
			if(!(mask >> i & 1)) {
				int nmask = mask ^ (1 << i);
				if(f(mask) == f(nmask) + !(sum[nmask] % target)) {
					ans.push_back(i);
					mask = nmask;
					if(sum[mask] % target == 0) {
						printf("%d", (int)ans.size());
						for(int x : ans) printf(" %d", p[x]);
						printf("\n");
						ans.clear();
					}
				}
			}
		}
	}
}