Untitled
plain_text
17 days ago
3.1 kB
1
Indexable
Never
package chuoi_mang_tong_k_; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int m, sum, n, res, check; static int[] a, visit, value; static int[][] kq; static void backtrack(int count, int start){ if(count > m){ return; } if(count == m){ int dem = 0; for(int i = 0; i < n ; i++){ if(visit[i] == 1){ kq[res][dem] = a[i]; dem++; } } res += 1; check = 1; return; } for(int i = start; i < n;i++){ if(visit[i] == 0){ visit[i] = 1; backtrack(count + a[i], i); visit[i] = 0; } } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { m = scanner.nextInt(); n = scanner.nextInt(); a = new int[n]; visit = new int[n]; kq = new int[n*n][n]; sum = 0; int max = 0; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); sum +=a[i]; if(a[i] > max){ max = a[i]; } } value = new int[max+1]; if(sum < m){ res = -1; }else{ res = 0; check = 0; backtrack(0, 0); if(check == 0){ res = -1; }else{ int[] find = new int[res]; int dem = res; for (int i = 0; i < dem; i++) { if(kq[i][0] != 0) for(int j = i+1; j < dem ;j++){ if(find[j] == 0){ int kt = 0; for(int p = 0; p < n;p++){ if(kq[i][p] != 0 && kq[i][p] != kq[j][p]){ kt = 1; break; } } if(kt == 0){ find[j] = 1; res --; } } } } for (int i = 0; i < dem; i++) { if(find[i] != 1){ for (int j = 0; j < n; j++) { System.out.print(kq[i][j] + " "); } System.out.println(); } } } } System.out.println("#" + t + " " + res); } scanner.close(); } } 20 644 12 54 80 97 20 47 98 68 28 25 55 2 70 498 12 60 70 15 4 32 44 93 37 21 25 38 59 150 12 9 93 72 64 9 27 47 24 3 26 75 3 499 11 57 33 43 12 42 35 8 61 49 73 86 734 11 55 89 23 28 81 58 90 77 72 64 97 302 12 61 100 72 28 7 26 18 60 70 61 62 39 295 11 82 31 72 46 97 98 61 13 17 47 26 201 10 62 63 2 46 39 95 71 58 69 99 133 10 66 55 48 89 28 83 18 20 100 28 272 11 55 24 43 94 38 78 68 3 25 94 22 171 12 35 54 64 67 29 13 81 26 3 43 58 40 207 12 49 73 4 62 18 40 95 69 35 33 96 49 429 10 53 25 60 30 36 35 15 100 69 6 226 10 68 51 75 64 13 75 85 96 60 92 626 12 45 65 11 81 40 80 83 21 60 65 28 47 407 12 79 96 81 82 42 45 89 90 88 72 38 13 152 12 80 51 59 94 35 63 15 14 89 18 68 25 350 12 1 73 75 58 86 64 49 52 88 60 45 49 261 10 38 90 71 16 33 82 36 91 42 23 692 10 100 87 93 69 29 53 62 76 50 73