How to find minimum elements in array which has sum equals to given value in java

Question

Elements from array which makes sum equals to given value

input array:[10,0,-1,20,25,30]
required sum:45
output:[20,25]

Answer 1

Please provide more sample test cases involving varying conditions so that I can create a good solution :)

Answer 2

You can do this..
Declare a variable say 'i' in a for loop.. Increment it's value by 1. Then use combinations (permutations and combinations.. That one) to find all the possible arrays of the no. Of elements equal to 'i'.
Then in all these arrays, find their sum, which should be equal to the input.

For python it's like:

import itertools

sum = int(input())
array = [1,73,91,5]
for i in range(1, len(array)+1):
for w in itertools.combinations(array, i):
if sum(w) == sum:
print(w)

Answer 3

@ganesh.. You just want a pair??? Like just 2 elements?

Answer 4

I want to help for this problem

Answer 5

arr[0] add to all element and check that condition ..acoording all the element add and check..then find easily value

Answer 6

@ jayshri I want to find pair of given array that match user value such as sum

Answer 7

Somasundaram K I think you defined sum as an integer elsewhere in the code that's why you're not able to use the built-in sum function

Answer 8

Somasundaram K since `i` starts from 1 and is increased till the length of the array, the first combination which you will get (whose sum is equal to the required sum) will be of the lowest size. So you already have that.

Answer 9

Can you post a new question on the Q&A section? Because this is off topic to this question Somasundaram K

Answer 10

different way to find the pair of that set..it's depend on you...which logic you can use

Answer 11

import java.util.*;
public class Solution
{
public static TreeMap<Integer,Object> map=new TreeMap<Integer,Object>();

// The vector v stores current subset.
static void printAllSubsetsRec(int arr[], int n, Vector<Integer> v,
int sum)
{
// If remaining sum is 0, then print all
// elements of current subset.
if (sum == 0) {
map.put(v.size(), v);
for (int i=0;i<v.size();i++)
System.out.print( v.get(i) + " ");
System.out.println();
return;
}

// If no remaining elements,
if (n == 0)
return;

// We consider two cases for every element.
// a) We do not include last element.
// b) We include last element in current subset.
printAllSubsetsRec(arr, n - 1, v, sum);
Vector<Integer> v1=new Vector<Integer>(v);
v1.add(arr[n - 1]);
printAllSubsetsRec(arr, n - 1, v1, sum - arr[n - 1]);
}

// Wrapper over printAllSubsetsRec()
static void printAllSubsets(int arr[], int n, int sum)
{
Vector<Integer> v= new Vector<Integer>();
printAllSubsetsRec(arr, n, v, sum);
}

// Driver code
public static void main(String args[])
{
int arr[] = {10,0,-1,20,25,30};;
int sum = 45;
int n = arr.length;
printAllSubsets(arr, n, sum);
System.out.println((Vector<Integer>)map.get(map.firstKey()));
}
}
//TC: 2^n

Answer 12

Good

Answer 13

Can some one help on this python program
import itertools

total = 78
array = [1,73,91,5]
for i in range(1, len(array)+1):
for w in itertools.combinations(array, i):
if sum(w) == total:
print (w)

but Im getting an error like this
TypeError Traceback (most recent call last)
<ipython-input-11-1720dfd2880f> in <module>
5 for i in range(1, len(array)+1):
6 for w in itertools.combinations(array, i):
----> 7 if sum(w) == total:
8 print ((w))

TypeError: 'int' object is not callable

Answer 14

@yash Yes your correct. Now the code is working good, but I want to find the minimum number of elements in array which has sum equals to the given value
Ex: array = [2,3,5]
sum = 11
minimum no of elements which gives output as 11, are 3 (5 + 3 +3) .
I am not able to get this o/p since the combinations function gives only unique combination of the list.

Answer 15

@Yash yes.. From the List[2,3,5] if i need a sum of 2 or 3 or 5 I will get it by the combinations but i need to add the elements repeatedly, if required[5 + 3 +3 ] = 11 (where sum is 11). (5 + 3 + 3) is the min no. of elements required to get sum of 11
How to get it...?

Answer 16

Only find sum of given array no other condition
like as
input array: [10,0,-1,20,25,30]
required sum : 29
output : [-1,30]

Answer 17

@ganesh plz give the solution...