Untitled

mail@pastecode.io avatar
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);
        }
    }
}