1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 574 Sum It Up
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=515
*
* @author Stefan Burgmair
* @author YYY
* @version 1.0, 26/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.452
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main
{
static ArrayList<String> output = new ArrayList<String>();
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

do{
String[] input = reader.readLine().split(" ");
int t = Integer.parseInt(input[0]);
int n = Integer.parseInt(input[1]);
if(!(n == 0 && t == 0)){
int[] numbers = new int[input.length - 2];
for (int i = 0; i < numbers.length; i ++){
numbers[i] = Integer.parseInt(input[i + 2]);
}
System.out.println("Sums of " + t + ":");

findSolutions(t,n,numbers,0, 0, "");
for (int f = 0; f < output.size(); f ++){
System.out.println(output.get(f));
}
if(output.size() == 0)
System.out.println("NONE");
output.clear();
}
}while (reader.ready());
}

public static void findSolutions(int t, int n, int[] numbers, int index, int sum, String task){
//System.out.println("t: " + t + " , n:" + n + " , index:" + index + " , sum:" + sum + " , task:" + task);
for (int i = index; i < n; i ++){
sum = sum + numbers [i];
//System.out.println(sum);
if (sum > t){

}else if (sum == t){
boolean unique = true;
String s;
if (task.equals(""))
s = String.valueOf(numbers [i]);
else
s = task + "+" + numbers [i];

for (int f = 0; f < output.size(); f ++){
//System.out.println("outputf: " + output.get(f) + " s: " + s);
if(s.equals(output.get(f)))
unique = false;
}
if(unique)
output.add(s);
//System.out.println("sum == t " + s + " " + unique);
}else{
String s;
if (task.equals(""))
s = String.valueOf(numbers [i]);
else
s = task + "+" + numbers [i];
findSolutions(t,n,numbers,i + 1,sum,s);
}
sum = sum - numbers [i];
}
}
}

2.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11 Problem: 574
 * Sum It Up Link:
 * http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=515
 *
 * @author Bastian Hoecker
 * @author Philipp Hauck Thalheim
 * @version 1.0, 04/27/2011
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.344
 */

public class Main {
   
    /**Parameter:
     * @param zahlen Summanden-Array
     * @param t die Summe
     * @param n Anzahl der Summanden
     * @param curPos derzeitiger Summand
     * @param cur derzeitge Summe
     * @param curS Ausgabestring
     * @param asdf String Set
    */
    static void calc(int[] zahlen, int t, int n, int curPos, int cur, String curS, Set<String> asdf) {
        if (cur == t) {
            if (!asdf.contains(curS.substring(1)))
                System.out.println(curS.substring(1));
            asdf.add(curS.substring(1));
            return;
        }
        if (cur > t) {
            return;
        }
        for (int i = curPos; i < n; i++) {
            calc(zahlen, t, n, i + 1, cur + zahlen[i], curS + "+" + zahlen[i], asdf);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        boolean finish = false;

        while (!finish) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            //Hash-Set zum rausschmeißen der doppelten Strings
            Set<String> asdf = new HashSet<String>();
            //Die zu Vergelichende Summe
            int t = Integer.parseInt(st.nextToken());
            //Anzahl der Summanden
            int n = Integer.parseInt(st.nextToken());
            //Abbruchbedingung
            if (n == 0)
                finish = true;
            //Summanden ins Array eintragen
            else {
                int[] zahlen = new int[n];
                for (int i = 0; i < n; i++) {
                    zahlen[i] = Integer.parseInt(st.nextToken());
                }
                //Ausgabe
                System.out.printf("Sums of %d:%n", t);
                //Aufruf der rekursiven Funktion
                calc(zahlen, t, n, 0, 0, "", asdf);
                //Ausganbe falls nichts zu Addieren geht
                if (asdf.isEmpty()) {
                    System.out.println("NONE");
                }
            }
        }
    }

}

--------------------------------

1.
/**
* Problem: 574 Sum It Up
* Zeit: 0.176
* Programmiersprache: JAVA
* @author Christoph Miesel
* Status: ACCEPTED
*/


import java.util.*;
import java.io.*;

public class Backtrack
{
static int[] array;
static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
static int counter = 0;
static int S,N;
static ArrayList<Integer> list = new ArrayList<Integer>();

static boolean compare(ArrayList<Integer> l1, ArrayList<Integer> l2)
{
if(l1.size() != l2.size())
return false;
else
{
for(int i = 0; i < l1.size(); ++i)
if(l1.get(i) != l2.get(i))
return false;
}
return true;
}

/** Back-Tracking algorithm */
static void backtrack(int sum, int index, int step)
{
if(sum > S)
{
return;
}

sum += array[index];
list.add(step, array[index]);

if(sum == S)
{
//System.out.println(list);
// make copy of one result
ArrayList<Integer> tmp = new ArrayList<Integer>();
for(int i = 0; i <= step; ++i)
tmp.add(list.get(i));
//System.out.println(list);
boolean isSol = true;

for(ArrayList l: res)
isSol &= !compare(tmp, l);
if(isSol)
{
res.add(tmp);
++counter;
}
list.remove(step);
return;
}

for(int i = index+1; i < array.length; ++i)
{
backtrack(sum, i, step+1);
}
list.remove(step);

}

public static void main(String[] args) throws IOException
{
// organization for reading the input

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer t = new StringTokenizer(r.readLine());
// reading the input
S = Integer.parseInt(t.nextToken());
N = Integer.parseInt(t.nextToken());

while(S != 0 || N != 0)
{
// fill the array with the number which wants to be summed up
array = new int[N];
for(int i = 0; i < N; ++i)
array[i] = Integer.parseInt(t.nextToken());

// computing all solutions with backtracking and saving every results in a list
for(int i = 0; i < array.length; ++i)
{
list.clear();
backtrack(0, i, 0);
}

// output the result
System.out.println("Sums of "+S+":");
if(counter == 0)
System.out.println("NONE");
else
for(ArrayList<Integer> h: res)
{
for(int i = 0; i < h.size(); ++i)
{
if(i < h.size()-1)
System.out.print(h.get(i)+"+");
else System.out.print(h.get(i));
}
System.out.println();
}

// reading new input
t = new StringTokenizer(r.readLine());
S = Integer.parseInt(t.nextToken());
N = Integer.parseInt(t.nextToken());
res.clear();
list.clear();
counter = 0;
}
}
}