By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,800 Members | 1,404 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,800 IT Pros & Developers. It's quick & easy.

combination code output needs explanation

P: 5
Expand|Select|Wrap|Line Numbers
  1. import java.util.ArrayList;
  2.     import java.util.List;
  3. public class CombinationApp {
  4.  
  5.         private static int[] numbers= {1,2,3,4,5,6,7,8,9,10};
  6.         private static int[] sumsum= new int[numbers.length];
  7.  
  8.         private static int sum= 10;
  9.  
  10.         private static void solution(List<Integer> solution) {
  11.  
  12.             System.out.println(solution);
  13.         }
  14.  
  15.         private static void solve(int[] numbers, int i, int sum, List<Integer> solution) {
  16.  
  17.             if (sum == 0) 
  18.                 solution(solution);
  19.             else
  20.                 for (; i < numbers.length && sumsum[i] >= sum; i++) {
  21.                     if (numbers[i] <= sum) {
  22.                         solution.add(0, numbers[i]);
  23.                         solve(numbers, i+1, sum-numbers[i], solution);
  24.                         solution.remove(0);
  25.                     }
  26.                 }
  27.         }
  28.  
  29.         public static void main(String[] args) {
  30.  
  31.             for (int s= 0, i= numbers.length; --i >= 0; ) {
  32.                 sumsum[i]= numbers[i]+s;
  33.                 s+= numbers[i];
  34.             }
  35.             solve(numbers, 0, sum, new ArrayList<Integer>());
  36.         }
  37.     }
  38.  
  39.  
why is it that this is the output ?
[4, 3, 2, 1]
[7, 2, 1]
[6, 3, 1]
[5, 4, 1]
[9, 1]
[5, 3, 2]
[8, 2]
[7, 3]
[6, 4]
[10]
Apr 3 '13 #1
Share this Question
Share on Google+
2 Replies


Rabbit
Expert Mod 10K+
P: 12,422
Because that combination of values adds up to the target number, in this case 10. Since it's a recursive function, it repeatedly calls itself to add every combination of numbers in the array until it hits the target value or runs out of numbers to add.
Apr 3 '13 #2

10K+
P: 13,264
It's a normal depth first algorithm so maybe revise that algorithm and have a look at the code again.
Here is a variation without the main method setup
Expand|Select|Wrap|Line Numbers
  1.     public static void main(String[] args) {
  2.         int[] numberlist = {1,2,3,4,5,6,7,8,9,10};
  3.         Set<String> answersList = new HashSet<String>();
  4.         findSums(numberlist, 0, 0, 10, "", answersList);
  5.         System.out.println(answersList);
  6.  
  7.     }
  8.  
  9.     public static void findSums(int[] list, int index, int current, int K, String previousList, Set<String> answers) {
  10.         if (list.length < index || current > K)
  11.             return;
  12.         for (int i = index; i < list.length; i++) {
  13.             if (current + list[i] == K) {
  14.                 answers.add(previousList + " " + list[i]);
  15.             } else if (current + list[i] < K) {
  16.                 findSums(list, i + 1, current + list[i], K, previousList + " " + list[i], answers);
  17.             }
  18.         }
  19.     }
  20.  
Apr 4 '13 #3

Post your reply

Sign in to post your reply or Sign up for a free account.