java - Finding all combinations of duplicates numbers to reach a given sum -

i want finding combinations in array reach given sum. example if array [1,1,1,2,4,4] , given target 5 should output be:

expected output 1 1 1 2 1 4 1 4 

this code far did:

static void sum(int[] arr, int i, int sum, int target, string s) {     (int j = + 1; j < arr.length; j++) {         if (sum + arr[j] == target) {             system.out.println(s + " " + string.valueof(arr[j]));         } else {             sum(arr, j, sum + arr[j], target, s + " " + string.valueof(arr[j]));         }     } }  public static void main(string[] args) {     int[] numbers = { 1, 1, 1, 2, 4, 4 };     (int = 0; < numbers.length; i++) {         sum(numbers, i, numbers[i], 5, string.valueof(numbers[i]));     }  } 

and output of code :

my output 1 1 1 2 1 4 1 4 1 4 1 4 1 4 1 4 

there problem when have duplicates elements , working non duplicates numbers, not when there duplicates numbers. want know how can solve problem output seems expected one.

one of basic objects need deal in problem bag or multiset - unordered set of values can contain multiple instances of element. unfortunately java collections framework doesn't support this. rather mess around trying list work can write our own basic version, capabilities need. (the guava library has multiset, production code).

import java.util.map; import java.util.nosuchelementexception; import java.util.treemap;  public class bag<e>  {     private map<e, integer> m_values;      public bag()     {         m_values = new treemap<e, integer>();     }      public bag(iterable<e> arr)     {         this();         for(e v : arr)         {             add(v);         }     }      public bag(bag<e> b)     {         this();         for(e v : b.values())         {             set(v, b.count(v));         }     }      public void add(e v)     {         integer count = m_values.get(v);         m_values.put(v, count == null ? 1 : count+1);     }      public void add(bag<e> b)     {         for(e v : b.values())         {             integer count = m_values.get(v);             m_values.put(v, count == null ? b.count(v) : count+b.count(v));         }     }      public void remove(e v)     {         integer count = m_values.get(v);         if(count == null) throw new nosuchelementexception();         if(count == 1)             m_values.remove(v);         else             m_values.put(v, count-1);     }      public void remove(bag<e> b)     {         for(e v : b.values())         {             integer count = m_values.get(v);                 integer bcount = b.count(v);             if(count == null || count < bcount) throw new nosuchelementexception();             if(count == bcount)                 m_values.remove(v);             else                 m_values.put(v, count-bcount);         }     }      public boolean contains(bag<e> b)     {         for(e v : b.values())         {             if(count(v) < b.count(v)) return false;         }         return true;     }      public void set(e v, int count)     {         if(count == 0)             m_values.remove(v);         else             m_values.put(v, count);     }      public int count(e v)     {         integer count = m_values.get(v);         return count == null ? 0 : count;     }      public iterable<e> values()     {         return m_values.keyset();     }      public string tostring()     {         stringbuilder b = new stringbuilder();         b.append("[");         for(e v : values())         {             for(int i=0; i<count(v); i++)             {                 b.append(v + " ");             }         }         b.deletecharat(b.length()-1);         b.append("]");         return b.tostring();     } } 

the first step in solving problem generate list of candidate sets sum 5. generating subsets input array, have careful not include duplicates. code isn't bad, it's easier, if little less efficient, generate possible partitions of count you're interested in, in case 5.

import java.util.arraylist; import java.util.list;  public class partition {     public static list<bag<integer>> partitions(int n)     {         return new partition(n).partitions;     }      private list<bag<integer>> partitions;     private bag<integer> current;      private partition(int n)     {         partitions = new arraylist<>();         current = new bag<integer>();         build(n, n);     }      private void build(int n, int max)     {         if (n == 0)         {             partitions.add(0, new bag<integer>(current));         }          (int = math.min(max, n); >= 1; i--)         {             current.add(i);             build(n - i, i);             current.remove(i);         }     }      public static void main(string[] args)     {         (bag<integer> b : partitions(5))         {             system.out.println(b);         }     } } 

output:

[1 1 1 1 1] [1 1 1 2] [1 2 2] [1 1 3] [2 3] [1 4] [5] 

now can write recursive routine extract maximal sets of these partitions input. tricky part ensure when find set isn't subset of solution we've seen, in case can ignore it.

import java.util.arraylist; import java.util.arrays; import java.util.list;  public class dice {     public static list<list<bag<integer>>> picks(integer[] dicearr, int k)     {         return new dice(dicearr, k).output;     }      private list<list<bag<integer>>> output;     private list<bag<integer>> current;      private list<bag<integer>> partitions;     private bag<integer> dice;      private dice(integer[] dicearr, int k)     {         output = new arraylist<>();         current = new arraylist<>();          partitions = partition.partitions(5);         dice = new bag<>(arrays.aslist(dicearr));          build(0);     }      private void build(int pos)     {         (int i=pos; i<partitions.size(); i++)         {             bag<integer> partition = partitions.get(i);              if(dice.contains(partition))             {                 dice.remove(partition);                 current.add(partition);                 build(i);                 current.remove(partition);                               dice.add(partition);             }                    }          // add current list of partitions if haven't seen         if(!current.isempty())         {             boolean seen = false;             for(list<bag<integer>> prev : output)             {                 if(prev.containsall(current))                  {                     seen = true;                     break;                 }             }             if (!seen) output.add(new arraylist<>(current));         }     }      public static void main(string[] args)     {         int count = 5;         integer[] dice = {1, 1, 1, 2, 4, 4};         list<list<bag<integer>>> picks = picks(dice, count);         for(list<bag<integer>> pick : picks)         {             system.out.println(pick);         }     } } 

output {1, 1, 1, 2, 4, 4}:

    [[1 1 1 2]]     [[1 4], [1 4]] 

output {1, 1, 1, 2, 3, 4, 4, 4, 5}:

[[1 1 1 2], [5]] [[1 1 3], [1 4], [5]] [[2 3], [1 4], [1 4], [1 4], [5]]