Untitled
unknown
plain_text
a year ago
1.5 kB
3
Indexable
Never
import java.util.*; public class FourthTask { public static List<Integer> findFinalSet(int[] arr, int N) { List<Integer> subset = new ArrayList<>(); findSet(arr, N, 0, subset); return subset; } private static boolean findSet(int[] arr, int t, int startIndx, List<Integer> subset) { if (t == 0) { return true; } if (t < 0 || startIndx >= arr.length) { return false; } subset.add(arr[startIndx]); if (findSet(arr, t - arr[startIndx], startIndx + 1, subset)) { return true; } subset.remove(subset.size() - 1); return findSet(arr, t, startIndx + 1, subset); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[] arr = new int[m*2]; for(int i = 0; i<m*2; i+=2){ arr[i] = scanner.nextInt(); arr[i+1] = arr[i]; } List<Integer> subset = findFinalSet(arr, n); if (subset.isEmpty()) { System.out.println("-1"); } else { System.out.println(subset.size()); StringBuilder ans = new StringBuilder(subset.get(0).toString()); for(int i = 1; i<subset.size(); i++){ ans.append(" ").append(subset.get(i)); } System.out.println(ans); } } }