LeetCode Subsets II 題解：含重複元素數組的所有子集生成（遞歸回溯去重）

題目大意

給定可能含重複元素的整數數組，返回所有不重複的子集。子集內元素非降序，解集無重複子集。例：[1,2,2] → [[],[1],[2],[1,2],[2,2],[1,2,2]]。

解法：排序 + 遞歸回溯 + 去重

先排序。遞歸函數 help(start) 從 start 開始嘗試添加元素。維護當前子集 list。每層遞歸前將 list 加入結果（用 HashSet 去重或同層跳過重複元素）。

Java 代碼

public class Solution {
    List> res = new ArrayList<>();
    List list = new ArrayList<>();
    public List> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        help(num, 0);
        return res;
    }
    private void help(int[] num, int start) {
        if (!res.contains(list)) {
            res.add(new ArrayList<>(list));
        }
        for (int i = start; i < num.length; i++) {
            list.add(num[i]);
            help(num, i+1);
            list.remove(Integer.valueOf(num[i]));
        }
    }
}

注：res.contains(list) 利用 List 的 equals 比較內容去重。更高效的寫法是在同層循環中 if (i > start && num[i] == num[i-1]) continue; 跳過重複元素。