найти минимальные элементы в массиве, равные сумме

Question

Я пытаюсь найти минимальные элементы в массиве, сумма которых равна заданному входу.Я попытался набрать несколько входных сумм, но смог найти только пару в первом случае, в то время как мне нужно было реализовать не только пару.

Массив ввода : [10, 0, -1, 20, 25, 30]

необходимая сумма : 45

Выход : [20, 25]

Я пытаюсь

Массив ввода : [10, 0, -1, 20, 25, 30]

Необходимая сумма : 59

Выход : [10, -1, 20, 30]

Answer 1

Возможно, я нашел решение, которое вы ищете

Я заметил, что ваша проблема может быть решена путем перебора всех возможных комбинаций в массиве (комбинации размера 2 с размером массива)

class A { 

    /* arr[]  ---> Input Array 
    data[] ---> Temporary array to store current combination 
    start & end ---> Staring and Ending indexes in arr[] 
    index  ---> Current index in data[] 
    r ---> Size of a combination to be printed */
    static void combinationUtil(int arr[], int data[], int start, 
                                int end, int index, int r, int ss ) 
    { 
        // Current combination is ready to be printed, print it 
        if (index == r) 
        { 
            int s = 0 ; 

            for (int j=0; j<r; j++) 
                s += data[j] ; 


            if(s==ss) 
            {
                for (int j=0; j<r; j++) 
                  System.out.print(data[j]+" "); 

                System.out.println(" "); 

            }

            return; 
        } 

        // replace index with all possible elements. The condition 
        // "end-i+1 >= r-index" makes sure that including one element 
        // at index will make a combination with remaining elements 
        // at remaining positions 
        for (int i=start; i<=end && end-i+1 >= r-index; i++) 
        { 
            data[index] = arr[i]; 
            combinationUtil(arr, data, i+1, end, index+1, r , ss); 
        } 
    } 

    // The main function that prints all combinations of size r 
    // in arr[] of size n. This function mainly uses combinationUtil() 
    static void printCombination(int arr[], int n, int r, int ss) 
    { 
        // A temporary array to store all combination one by one 
        int data[]=new int[r]; 

        // Print all combination using temprary array 'data[]' 
        combinationUtil(arr, data, 0, n-1, 0, r, ss); 
    } 

    /*Driver function to check for above function*/
    public static void main (String[] args) { 
        int arr[] = {10,0,-1,20,25,30} ; 

        int n = arr.length; 
        int ss = 59 ; 

        for( int i = 0 ; i < arr.length ; i++ ) 
          printCombination(arr, n, i, ss); 
    } 
} 

Я нашел алгоритм комбинаций в https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

и изменил его, чтобы он соответствовал вашей проблеме

Я надеюсь, что это поможет