CODEWITHSUNDEEP
javaarraysalgorithm
kirtan403
kirtan403

Reputation: 7411

Pick from array which is equal to some number

I have an array of amounts something like this:

[ 100, 20, 80, 50, 150, 20, 10 .. ]

I have to pick from this array which is equal to some amount, say 200.

So, the amounts will be 150, 50 picked from the array.

I can build an algorithm which can iterate through the array again and again and check if amount is equal or not, but I want to know if is there an easy way?

Or I have to write an algo matching in loop and picking and checking?

Thanks.

Example explanation:

I have an array. Say -> 100, 200, 300

I have a another array. Say -> 50,50,20,10,20,150,150,50,70,30

I want to match by picking up a number from the first array(i.e 100) and matching by sum of numbers from the second array if it matches, else fine, I will skip it and try it for the next number (i.e. 200) in the array.

EDIT: Some clarification

The array does not contain the exact matches. I matched it previously and removed from the array. So it only contains numbers that can be exactly the same.

It is fine if any sum is not matched by the given amount. I will simply skip if sum from array doesn't match.

Upvotes: 0

Views: 552

Answers (4)

Sergei Rybalkin
Sergei Rybalkin

Reputation: 3453

Algorithm:

def solve(subList: List[Int], ammount: Int) = ammount match {
  case 0 => true
  case _ => sublist match {
    case Nil => false 
    case x::xs => {
      val rest = ammount - x
      solve(xs, ammount) || rest >= 0 && solve(xs, rest)
    }
  }
}


solve(list, ammount)

Explanation:

You can get ammount in list:

  1. if you take first element and can get ammount - first element within list without first element

  2. if you doesn't take first element and you can get ammount within list without first element

So we have reduction on each step of recursion.

We terminate with true when ammount is collected and with false when sublist is empty with non-zero ammount.

Example: from (50,50,20,10,20,150,150,50,70,30) need 100: solve((50,50,20,10,20,150,150,50,70,30), 100)

We can if 

solve((50,20,10,20,150,150,50,70,30), 100) == true || solve((50,20,10,20,150,150,50,70,30), 50) == true

next step: from (50,20,10,20,150,150,50,70,30) need 50

solve((50,20,10,20,150,150,50,70,30), 50)

We can if 

solve((20,10,20,150,150,50,70,30), 0) == true || solve((20,10,20,150,150,50,70,30), 50) == true

first one is true => terminate

Upvotes: 2

mtszkw
mtszkw

Reputation: 2783

The problem you try to solve is called subset sum problem and belongs to NP-complete problems.

Given a set of integers and an integer s, does any non-empty subset sum to s (...)

No polynomial-time algorithm to solve this problem is known (at the moment ;)).
You can check all subsets of your set which is O(2^n) if your set contains n elements.
Eventually if your set would be an infinite set, you could try solving the change-making problem.

Still it can be solved (exponential complexity as I wrote above). Consider a function:

bool foundSum(set[], n, sum);

which returns true if the sum can be found, false otherwise. A simple recursive algorithm:

foundSum(set,n,sum) = foundSum(set,n-1,sum) or foundSum(arr,n-1,sum-set[n-1])

How it works? In each step you check if the sum can be obtained if you in/exclude last element.

Example implementation in C++ (can be easily written in Java):

bool foundSum(vector<int> set, int n, int sum) {
    if(sum == 0) return true;
    if(n == 0 and sum != 0) return false;

    int last = set[n-1];

    if(last > sum) return foundSum(set, n-1, sum);
    return foundSum(set,n-1,sum) or foundSum(set,n-1,sum-last);
}

Modified to print subset when answer is found: http://ideone.com/YysY2n

Upvotes: 2

omkar sirra
omkar sirra

Reputation: 726

Find all the possible subsets and check If any of the subset sum 
will match with the target amount.

Update

Its better to calculate the sum immediately and checking after finding each subset. So that 
we could skip atleast few subsets finding them.

Upvotes: 0

Melv_80
Melv_80

Reputation: 222

I believe best way to find out which indices have to be picked to reach your sum is having the amounts sorted in an array. (e.g. build them up sorted if this is possible)

then you can iterate until you hit the sum and abort if you are over it.

However, a bit more of context would be helpful, since this task does not seem very useful ..

Upvotes: 0

Related Questions