Untitled
unknown
plain_text
a year ago
1.6 kB
2
Indexable
Never
import java.util.ArrayList; import java.util.List; public class FourthTask { public static List<Integer> findSubsetSum(int[] arr, int N) { List<Integer> subset = new ArrayList<>(); findSubset(arr, N, 0, subset); return subset; } private static boolean findSubset(int[] arr, int target, int startIndex, List<Integer> subset) { if (target == 0) { return true; // Найдена комбинация элементов, сумма которых равна N } if (target < 0 || startIndex >= arr.length) { return false; // Невозможно найти комбинацию элементов } // Пробуем включить текущий элемент в комбинацию subset.add(arr[startIndex]); if (findSubset(arr, target - arr[startIndex], startIndex + 1, subset)) { return true; } // Если не нашли комбинацию с текущим элементом, удаляем его и пробуем без него subset.remove(subset.size() - 1); return findSubset(arr, target, startIndex + 1, subset); } public static void main(String[] args) { int[] arr = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 23}; int N = 46; List<Integer> subset = findSubsetSum(arr, N); if (subset.isEmpty()) { System.out.println("NO"); } else { System.out.println("YES " + N + ": " + subset); } } }