Untitled

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