Untitled
unknown
plain_text
a year ago
1.8 kB
4
Indexable
Never
public class Main { public static List<Integer> findElementsForSum(int[] nums, int k) { int n = nums.length; boolean[][] dp = new boolean[n + 1][k + 1]; for (int i = 0; i <= n; i++) { dp[i][0] = true; } boolean[][] included = new boolean[n + 1][k + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { if (j >= nums[i - 1]) { if (dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]) { dp[i][j] = true; included[i][j] = true; } } else { dp[i][j] = dp[i - 1][j]; } } } List<Integer> elementsForSum = new ArrayList<>(); int i = n, j = k; while (i > 0 && j > 0) { if (included[i][j]) { elementsForSum.add(nums[i - 1]); j -= nums[i - 1]; } i--; } return elementsForSum; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int neededSum = scanner.nextInt(); int numberOfMoney = scanner.nextInt() * 2; int[] nums = new int[numberOfMoney]; for (int i = 0; i < numberOfMoney; i += 2) { nums[i] = scanner.nextInt(); nums[i + 1] = nums[i]; } long startTime = System.nanoTime(); List<Integer> elements = findElementsForSum(nums, neededSum); long endTime = System.nanoTime(); if (!elements.isEmpty()) { System.out.println(elements); } else { System.out.println(-1); } } }