0

Example:

Input: 3, 6, 3 Output: True (since 3 + 3 = 6)

Input: 3, 2, 6, 4 Output: False (since no combination will result in equality)

Input: 4, 7, 3, 6 Output: True (since 4 + 6 = 7 + 3)

can you guys give me an idea on how to code this? i've started on how to code this but i'm confused on how I can add the numbers and compair them

4
  • You mean divide the given array into two subgroups such that the sum of one group equals that of another group?
    – taocp
    Mar 14, 2013 at 2:42
  • i've started on how to code this but i'm confused on how I can add the numbers and compair them
    – Ryan Tan
    Mar 14, 2013 at 2:44
  • 3
    It is known as partition problem, which is NP-complete, you can find more information from this post: stackoverflow.com/questions/5292162/partition-problem
    – taocp
    Mar 14, 2013 at 2:54
  • umm. my bad I meant that if I add two numbers and compare it to another one it would return. as seen as on the example above. I have been trying to code it for a while now but I couldn't get the algorithm of the problem.
    – Ryan Tan
    Mar 14, 2013 at 3:00

5 Answers 5

3

I'll explain how a person could work on this without knowing magic words (like "partition problem", "dynamic programming", etc.) with which to consult some big book of answers (like Wikipedia).

If you take one instance of the largest not-yet-used number from the input and assign it to one of your two groups, then you have reduced the problem to a smaller instance of (a generalized version of) the same problem.

The generalized problem is, can you divide the input numbers into two groups such that the difference between the two groups' sums is a particular non-negative integer?

Let's say our input numbers are 4, 3, 2, 1 and we need to make two groups so that the difference between the groups' sums is 0.

We assign 4 to one of the groups, and in this particular case it doesn't matter which group.

Now our remaining input numbers are 3, 2, 1 and, ignoring the 4 that we already dealt with, we need to make these three numbers into two groups so that the difference between the groups' sums is 4. (That will balance out the difference between the two groups that we created by assigning the 4 to one of the groups.) As promised, this is a smaller instance of the original type of problem.

The difficulty is that sometimes, such as with 5, 5, 4, 3, 3 (example found in Wikipedia "Partition problem"), it's not obvious which group the next number needs to go into. If you keep track of what you've done, then when you find out your latest attempt didn't work, you can come back ("backtrack") and try the other way.

5, 5, 4, 3, 3 {} {}
   5, 4, 3, 3 {5} {}
      4, 3, 3 {5} {5}
         3, 3 {5, 4} {5}
            3 {5, 4} {5, 3}
              {5, 4} {5, 3, 3} NO - backtrack
              {5, 4, 3} {5, 3} NO - backtrack
            3 {5, 4, 3} {5}
              {5, 4, 3} {5, 3} NO - already tried - backtrack
              {5, 4, 3, 3} {3} NO - backtrack
         3, 3 {5} {5, 4} NO - symmetric to what we already tried - backtrack
      4, 3, 3 {5, 5} {}
         3, 3 {5, 5} {4}
            3 {5, 5} {4, 3}
              {5, 5} {4, 3, 3} YES

Will we be able to get the answer quickly? Well, this isn't the question that was asked, but in light of the complexity of backtracking, it's natural to ask. And the answer turns out to be, no, not even if we have the smartest person in the history of the world working for us. No one has ever found a method that is guaranteed to perform quickly no matter what instance of this kind of problem we give it. Maybe we can do pretty well for many instances of these problems, but in general and on average, a program to do this sort of thing is destined to be slow.

2
  • I do not see how it's helpful.
    – PM 77-1
    Mar 14, 2013 at 2:50
  • Yes, I was thinking about loop with backtrack myself, since I was ignorant of "Partition problem".
    – PM 77-1
    Mar 14, 2013 at 17:36
2

This is the partition problem, which is NP-complete. Despite that, there's a dynamic programming solution that you can use. See the Wikipedia article.

http://en.wikipedia.org/wiki/Partition_problem

0
public class Weirdie {
private boolean calculate(int[] array) {
    boolean match = false;
    List<Integer> list = new ArrayList<Integer>();
    int length = array.length;
    for(int i=0;i<length;i++) {
        for(int j=i+1;j<length;j++) {
            int sum = array[i] + array[j];
            if(list.contains(sum)) {
                match = true;
                break;
            } else {
                list.add(sum);
            }
        }
        if(match) {
            break;
        }
    }
    return match;
}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 3, 6, 3, 4, 8};
    int[] array2 = { 3, 2, 6, 4};
    int[] array3 = { 4, 7, 3, 6 };
    Weirdie  w = new Weirdie();
    System.out.println(w.calculate(array));
    System.out.println(w.calculate(array2));
    System.out.println(w.calculate(array3));
}

}

Actually I still confusing with your requirement.As your description,number group 1 {3,6,3} will output true because of 3+3=6.And you said number group 2 {3,2,6,4} will output false,but appearently 2+4=6 is also match your condition.With your third number group,I think the reason why number group 1 output true is 3+6=6+3.

1
  • it's because when you have only three digits inputted, you can compare two combined digits to a already higher digit that doesn't need adding. Where as when you inputted four digits you need to add them and then compare them all and see if one of the added digits are equal so that it could return true
    – Ryan Tan
    Mar 14, 2013 at 18:28
0

To determine is a array can be divided into two equal summed arrays, we can also find a subset which has half the sum of the whole array.

For e.g: Input: 4, 7, 3, 6

We should find a sub set whose sum == 10, which is a simple DP prob.

public static boolean isSubset(int[] a, int sum, int n) {

  if(sum == 0)
    return true;
  if(n<0)
    return false;
 return isSubset(a, sum-a[n], n-1) || isSubset(a, sum, n-1);
}
0

OK! just use brute force calculation, my checking every possible option

int[] numbersArray = new int[10];
int sum = 0;

for(int j = 0; j < numbersArray.lenght;j++) // sum
   sum += numbersArray[j];



for(int i = 0; i < numbersArray.lenght;i++)
{
   int numChecking =  numbersArray[i]; // right half .. 

   if((sum-numChecking) == numChecking)
     return true;

}
return false;

// i haven't tested it but, this will check all possibility's for 1 value..

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.