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

Question

как найти наименьшее число целых чисел в массиве, которое суммирует данное число. Программа должна попросить пользователя ввести массив целых чисел («Input Array») и требуемую сумму («Required Sum»). Выходные данные («Output») должны содержать наименьшее число целых чисел из входного массива, в котором суммируется «Required Sum».

здесь я создаю функцию sum () и объявляю массив с некоторыми элементами при чтении суммы от пользователя 45 , это дает мне вывод 25,25 , но когда я ввод 59 и 60 на выходе ничего не отображается

 public static void sum()
{


int arr[]={10,0,-1,20,25,30};
Scanner in=new Scanner(System.in);
int sum=in.nextInt();

int[] sub = new int[arr.length];
int temp = 0;
        for (int i = 0; i < arr.length; i++)
        {
            for (int j = i, col = 0; j < arr.length; j++, col++)
            {
                //add the value of input array one by one
                temp += arr[j];
                sub[col] = arr[j];
                   //if addition is equal to sum then print it
                 if (temp == sum)
                {
                  int total = 0;
                   for (int k = 0; k < sub.length; k++)
                  {
                          total += sub[k];
                       System.out.println(sub[k]);

                       //if total and sum are equal then leave the print
                        if (total == sum)
                        {
                               System.out.println();
                            break;
                        }
                     }
                }
                //if temp is greater than sum are equal then clear the sub array, set temp value and leave the loop for next
               if (temp > sum)
                {
                    temp = 0;
                   break;
                }
            }
        }

}

Пример вывода:

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

Необходимая сумма: 45 Вывод: [20, 25]

Необходимая сумма: 59 Вывод: [10, -1, 20, 30]

Необходимая сумма: 60 Выход: [10, 20, 30]

Answer 1

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

import java.util.*;
public class Main{


    public static void set(int[] temp,int sum){
     int n=temp.length;

        for (int i = 0; i < (1<<n); i++) 
        {  int sumc=0;
        int count=0;
            System.out.print("{ "); 

            // Print current subset 
            for (int j = 0; j < n; j++) 

                // (1<<j) is a number with jth bit 1 
                // so when we 'and' them with the 
                // subset number we get which numbers 
                // are present in the subset and which 
                // are not 
                if ((i & (1 << j)) > 0) {
                    System.out.print(temp[j] + " "); 
                    sumc=sumc+temp[j];     
                    count++;
                }
                if(sum==sumc){
            System.out.println("}"+" sum :"+sumc +" solution with "+count+" elements"); 
                }else{
                    System.out.println("}");
                }
        } 


    }



    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        System.out.println("enter size of array : ");
        int n=sc.nextInt();
        int[] a=new int[n];


        int sum;
        for(int i=0;i<n;i++)
        {
            System.out.print("enter "+i+" element value of array : ");
            a[i]=sc.nextInt();
            System.out.println();
        }
        System.out.println("enter sum : ");
        sum=sc.nextInt();
        set(a,sum);
    }
}

вывод:

Answer 2

import java.util.*;
public class Runner
{

    public static void find(int[] A, int currSum, int index, int sum,int[] solution) 
    {
            if (currSum == sum) 
        {

                  System.out.print("Output: [");
                  for (int i = 0; i < solution.length; i++) 
            {
                        if (solution[i] == 1) 
                {
                    if(A[i]!=0)
                    {
                                System.out.print("  " + A[i]);
                    }
                        }
                }
                  System.out.print(" ]\n");

            }
     else if (index == A.length) 
        {
                  return;
            } 
        else 
        {
                  solution[index] = 1;// select the element
                  currSum += A[index];
                  find(A, currSum, index + 1, sum, solution);
                  currSum -= A[index];  
                  solution[index] = 0;// do not select the element
                  find(A, currSum, index + 1, sum, solution);
            }
          return;
      }


    public static void main(String args[])
    {
        Scanner in =new Scanner(System.in);
        System.out.println("How many integer you have to insert: ");
        int n=in.nextInt();
        int []A=new int[n];
        System.out.println("\nEnter elements in Array:\n ");
        for(int i=0;i<A.length;i++)
        {
            A[i]=in.nextInt();
        }
        System.out.println("\nEnter required sum: ");
        int sum=in.nextInt();
            int[] solution = new int[A.length];
            find(A, 0, 0, sum, solution);
    }
}

Answer 3

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;


public class Subset {

    static public void main (String[] ab)
    {
        int s[] = {10, 0, -1, 20, 25, 30};
        int sum = 45;
        ArrayList<ArrayList<Integer>> lis = subsets(s,sum);
        Iterator<ArrayList<Integer>> t1 = lis.iterator();
        while (t1.hasNext()) {
            List<Integer> t2= t1.next();
            int count = 0;
            Iterator<Integer> t3 = t2.iterator();
            while (t3.hasNext()) {
                count = count+ t3.next();
            }
            if(count ==sum)
                System.out.println(t2);
        }

    }

    public static  ArrayList<ArrayList<Integer>> subsets(int[] S,int sum) {
        if (S == null)
            return null;

        Arrays.sort(S);

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < S.length; i++) {
            ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();

            //get sets that are already in result
            for (ArrayList<Integer> a : result) {
                temp.add(new ArrayList<Integer>(a));
            }

            //add S[i] to existing sets
            for (ArrayList<Integer> a : temp) {
                a.add(S[i]);
            }

            //add S[i] only as a set
            ArrayList<Integer> single = new ArrayList<Integer>();
            single.add(S[i]);
            temp.add(single);

            result.addAll(temp);
        }

        //add empty set
        result.add(new ArrayList<Integer>());

        return result;
    }
}

Надеюсь, это было полезно.