In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Beim Subset-Sum-Problem geht es darum, aus einer Liste von Zahlen eine Teilmenge auszuwählen, deren Summe genau einer Zielzahl entspricht.

Das Problem ist bekannt, weil es sehr gut zeigt, wie man mit Kombinationen arbeitet: Man entscheidet bei jeder Zahl, ob man sie nimmt oder weglässt.

In diesem Artikel lernst du eine einfache rekursive Lösung (Variante A) und eine Alternative, die oft besser zum Debuggen und Verstehen ist (Variante B mit Backtracking und einer konkreten gefundenen Kombination).

Wichtig: Wir betrachten hier bewusst kleines n (z.B. bis 20 oder 25 Werte), weil die Anzahl möglicher Teilmengen schnell wächst.

 

Problemstellung

Gegeben sind ein Array ganzer Zahlen und eine Zielsumme. Gesucht ist, ob es irgendeine Teilmenge gibt, deren Summe genau die Zielsumme ergibt.

  • Jedes Element darf höchstens einmal verwendet werden (Teilmenge, keine Wiederholungen).
  • Die Reihenfolge ist egal (es geht um Auswahl, nicht um Permutationen).
  • Wir lösen das für kleines n, also wenige Elemente.

Mini-Beispiel

  1. Zahlen: [3, 2, 7], Ziel: 5
  2. Mögliche Teilmengen: [], [3], [2], [7], [3,2], [3,7], [2,7], [3,2,7]
  3. Treffer: [3,2] ergibt 5

 

Die Idee dahinter

Das Kernkonzept sind Kombinationen per Rekursion: Bei jedem Element triffst du genau zwei Entscheidungen:

  • Nimm das aktuelle Element: Ziel wird kleiner.
  • Lass weg das aktuelle Element: Ziel bleibt gleich.

Das wiederholt sich, bis du entweder die Zielsumme erreicht hast (Erfolg) oder keine Elemente mehr übrig sind (Misserfolg).

Als kleine Visualisierung (Entscheidungsbaum fuer [3,2,7], Ziel 5):

  • Starte bei Index 0, Ziel 5
  • Entscheidung 1 (Zahl 3): nehmen (Ziel 2) oder weglassen (Ziel 5)
  • Entscheidung 2 (Zahl 2): nehmen oder weglassen
  • Entscheidung 3 (Zahl 7): nehmen oder weglassen

 

Schritt für Schritt zur Lösung

  1. Starte bei Index 0 und mit der Zielsumme target.
  2. Abbruch 1: Wenn target == 0, hast du eine passende Teilmenge gefunden.
  3. Abbruch 2: Wenn du am Ende des Arrays bist (index == values.length), geht es nicht mehr weiter.
  4. Probiere rekursiv den Fall ohne aktuelles Element (Index + 1, Ziel unverändert).
  5. Probiere rekursiv den Fall mit aktuellem Element (Index + 1, Ziel um values[index] reduziert).
  6. Wenn einer der beiden Wege true liefert, ist die Antwort true.

 

Java-Implementierung (Variante A: straightforward)

public class SubsetSumStraightforward {

  public static void main(String[] args) {
    int[] values1 = {3, 2, 7};
    int target1 = 5;

    int[] values2 = {1, 4, 6};
    int target2 = 5;

    System.out.println("values1 target1 => " + existsSubsetSum(values1, target1));
    System.out.println("values2 target2 => " + existsSubsetSum(values2, target2));
  }

  public static boolean existsSubsetSum(int[] values, int target) {
    return existsFrom(values, 0, target);
  }

  private static boolean existsFrom(int[] values, int index, int remaining) {
    if (remaining == 0) {
      return true;
    }

    if (index == values.length) {
      return false;
    }

    // Option 1: skip current value
    if (existsFrom(values, index + 1, remaining)) {
      return true;
    }

    // Option 2: take current value
    return existsFrom(values, index + 1, remaining - values[index]);
  }
}

Diese Variante ist bewusst sehr direkt: zwei rekursive Aufrufe, zwei Abbruchbedingungen. Der Vorteil: du siehst die Kernidee ohne Ablenkung. Der Nachteil: du bekommst nur true/false, aber nicht, welche Werte die Summe gebaut haben. Ausserdem wächst die Laufzeit schnell, weil viele Kombinationen ausprobiert werden.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List;

public class SubsetSumBacktracking {

  public static void main(String[] args) {
    int[] values = {3, 2, 7, 1};
    int target = 6;

    Result result = findSubsetSum(values, target);

    System.out.println("exists => " + result.exists());
    System.out.println("subset => " + result.subset());
    System.out.println("sum    => " + sum(result.subset()));
  }

  public static Result findSubsetSum(int[] values, int target) {
    List current = new ArrayList<>();
    List found = new ArrayList<>();

    boolean ok = backtrack(values, 0, target, current, found);

    if (!ok) {
      return new Result(false, List.of());
    }

    return new Result(true, Collections.unmodifiableList(found));
  }

  private static boolean backtrack(int[] values,
                                   int index,
                                   int remaining,
                                   List current,
                                   List found) {
    if (remaining == 0) {
      found.clear();
      found.addAll(current);
      return true;
    }

    if (index == values.length) {
      return false;
    }

    // Optional pruning for non-negative inputs: if remaining < 0, we can stop early.
    // This is only correct if all values are >= 0.
    if (remaining < 0) {
      return false;
    }

    // Option 1: skip
    if (backtrack(values, index + 1, remaining, current, found)) {
      return true;
    }

    // Option 2: take
    current.add(values[index]);
    boolean ok = backtrack(values, index + 1, remaining - values[index], current, found);
    current.remove(current.size() - 1);

    return ok;
  }

  private static int sum(List values) {
    int s = 0;

    for (int v : values) {
      s += v;
    }
    return s;
  }

  public record Result(boolean exists, List subset) {
  }
}

Hier siehst du Backtracking: Wir bauen eine aktuelle Auswahl current auf und nehmen sie wieder zurück, wenn ein Pfad nicht passt. Das ist oft leichter nachzuvollziehen, weil du eine konkrete Teilmenge bekommst. Zusätzlich ist eine kleine Optimierung möglich: Wenn alle Werte nicht-negativ sind, kannst du bei remaining < 0 früh abbrechen.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1:

  • Eingabe: values=[3,2,7], target=5
  • Output: true (z.B. Teilmenge [3,2])

Beispiel 2:

  • Eingabe: values=[1,4,6], target=5
  • Output: true (z.B. Teilmenge [1,4])

Beispiel 3:

  • Eingabe: values=[2,4,6], target=5
  • Output: false

 

Typische Fehler

  • Falsche Abbruchbedingung: remaining == 0 muss sehr früh geprüft werden, sonst verpasst du exakte Treffer.
  • Index-Fehler: index == values.length muss vor dem Zugriff auf values[index] abgefangen werden.
  • Backtracking vergessen: Bei Variante B muss nach current.add(...) immer ein passendes remove kommen, sonst bleibt der Zustand "hängen".
  • Pruning falsch eingesetzt: remaining < 0 darfst du nur als Abbruch nutzen, wenn alle Werte >= 0 sind. Mit negativen Zahlen wäre das falsch.
  • Teilmenge mit Teilfolge verwechseln: Subset-Sum erlaubt das Weglassen beliebiger Elemente, nicht nur zusammenhängende Bereiche.
  • Duplizierte Werte falsch interpretiert: Wenn values gleiche Zahlen enthält, sind das trotzdem verschiedene Positionen. "Einmal pro Element" bezieht sich auf den Index, nicht auf den Zahlenwert.

 

Fazit

Du hast gesehen, wie Subset-Sum mit Kombinationen und Rekursion funktioniert: bei jedem Element "nehmen oder weglassen". Variante A ist die kleinste, klarste Basislösung. Variante B zeigt Backtracking und liefert dir zusätzlich eine konkrete Teilmenge, was beim Lernen und Debuggen sehr hilfreich ist.