HDU 1258 Sum It Up：子集和輸出所有組合 (DFS 去重)

問題描述

給定目標和 t 和 n (≤12) 個非遞增排列的正整數（可能重複）。找出所有和為 t 的不同組合（每個數最多用其出現次數）。輸出按字典序降序：先比較第一個數，再第二個… 相同組合僅輸出一次。無解輸出 NONE。

解法：DFS + 剪枝去重

因數組已非遞增排序，直接按順序遞歸選或不選。關鍵去重：同一遞歸層（同一位置），若當前數等於前一個數且前一個數未被選入當前組合，則跳過當前數。這確保相同數值在同一位置只出現一次選擇路徑。

遞歸參數

• idx：當前考慮的數組下標。
• sum：當前累計和。
• path：當前選擇的數列表。

終止：sum == t → 輸出；sum > t 或 idx == n → 返回。

參考代碼 (Java)

import java.util.*;

public class SumItUp {
    static int t, n;
    static int[] a = new int[15];
    static List path = new ArrayList<>();
    static boolean found;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            t = sc.nextInt(); n = sc.nextInt();
            if (t == 0 && n == 0) break;
            for (int i = 0; i < n; ++i) a[i] = sc.nextInt();
            System.out.println("Sums of " + t + ":");
            found = false;
            path.clear();
            dfs(0, 0);
            if (!found) System.out.println("NONE");
        }
    }

    static void dfs(int idx, int sum) {
        if (sum == t) {
            found = true;
            for (int i = 0; i < path.size(); ++i) {
                if (i) System.out.print("+");
                System.out.print(path.get(i));
            }
            System.out.println();
            return;
        }
        if (idx == n || sum > t) return;
        int prev = -1;
        for (int i = idx; i < n; ++i) {
            if (a[i] == prev) continue; // 去重
            if (sum + a[i] > t) continue;
            path.add(a[i]);
            dfs(i + 1, sum + a[i]);
            path.remove(path.size() - 1);
            prev = a[i];
        }
    }
}

關鍵點

• 輸入已排序，DFS 自然產生非遞增序列，滿足輸出順序要求。
• prev 變量實現同層去重：同一 dfs 調用中，相同值只取第一個未用過的。
• n ≤ 12，最多 2^12 = 4096 子集，DFS 瞬時完成。

總結

• 經典子集和枚舉，輸入有序 + 同層去重 = 自動滿足輸出格式與去重。
• Java ArrayList 做路徑回溯簡潔高效。
• 注意多測試案例格式：每案例首行 Sums of t:。