import java.util.*; public class SumN2{ //given numbers private int[] arr; //target value private int value; public SumN2(int[]arr , int v ){ this.arr = arr; this.value = v; } public static void main(String[] args){ //test case 1 int[] arr = {13,17,99,71,7,1,66,73,53,529,4, 71, 70, 19}; int[] targets = {3,25,35}; int c = 1; for(int t : targets){ System.out.println("Sample " + (c++)); SumN2 s = new SumN2(arr,t); s.process(); } } public void process(){ //compute the number of choices to insert pluses long N = (long)Math.pow( 2 , this.arr.length); //list of possible solutions List> solutions = new ArrayList>(); for(int i=0;i sol = new ArrayList(); for(int index = arr.length - 1; index>=0;index--){ int rmd = (int) ( 1 & mask); mask = mask >> 1; if(rmd == 1){ sum+= arr[index] ; sol.add(arr[index]); } } if(sum == this.value){ solutions.add(sol); } } if(solutions.size()==0){ System.out.println("Impossible for value:" + this.value); }else for(int i=0;i" + format(solutions.get(i)) + "=" + this.value); } public String format(List sol){ Collections.sort(sol); StringBuffer sb = new StringBuffer(); for(int n : sol){ sb.append(n).append(" "); } return sb.toString(); } }