找到数组中的最小元素等于sum

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/找到了组合算法

我修改它以适应您的问题

我希望它有所帮助