Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
8
Indexable
public class Solution {
	static int sum, n;
	static int[] a;
	static int dem;
	static int[] res;
	static int[] ts;
	static int[] b;
	static int[] visit;
	static int m;

	public static void main(String args[]) throws Exception {
		int T;
		int Answer;
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			sum = sc.nextInt();
			n = sc.nextInt();
			a = new int[n];
			res = new int[n];
			ts = new int[105];
			b = new int[n];
			visit = new int[105];
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}

			m = 0;

			for (int i = 0; i < n; i++) {
				if (visit[a[i]] == 0) {
					visit[a[i]] = 1;
					b[m] = a[i];
					m++;
				}
				ts[a[i]]++;
			}

			for (int i = 0; i < m; i++) {
				System.out.println(b[i] + " " + ts[b[i]]);
			}

			dem = 0;
			Try(0, 0, 0, 0);
			System.out.println(dem);
		}
	}

	public static void Try(int k, int cnt, int u, int start) {
		if (cnt > sum) {
			return;
		}

		if (u == n) {
			if (cnt == sum) {
				dem++;
			}
			return;
		}

		if (cnt < sum) {
			for (int i = start; i < ts[b[k]]; i++) {
				Try(k, cnt + b[k], u + 1, start + 1);
			}
		} else {
			Try(k + 1, cnt + b[k], u + 1, start + 1);
		}
		Try(k + 1, cnt, u + 1, 0);
	}
}
Editor is loading...
Leave a Comment