Subset

題目要求找出所有的 subset 可能，空集合也算是一種，看到找出所有的可能答案直覺就是要用 DFS

以前看到這種題目會很慌，因為覺得自己怎麼都不會、怎麼都想不出來、遞迴都不會做

然後就很懊惱和沮喪，因為有些同學反應較快，很快就想通，

還有有同學瞧不起沒有第一次做完的人.....甚至還有學長直接說不會的是廢物....

不過只要自己每次看都看懂，最後學會就好，沒必要在意是不是自己想出來的，重要的是最後是不是真的懂了

覺得學演算法是一種修行，一點一滴累積功力，最後才知道是誰在笑！

話題拉回來，這題就是每次遞迴時丟一個數進去，因為沒有重複的數字，所以每一回合的結果都存下來就是答案了

public List<List<Integer>> subsets(int[] nums) {

    List<List<Integer>> results = new ArrayList<>();
    if (nums == null) {
        return results;
    }
    if (nums.length == 0) {
        results.add(new ArrayList<Integer>());
        return results;
    }

    Arrays.sort(nums);
    ArrayList<Integer> current = new ArrayList<Integer>();
    helper(nums, results, current, 0);
    return results;
}

void helper(int[] nums, List<List<Integer>> results,
            ArrayList<Integer> current, int start) {

    results.add(new ArrayList(current));
    // if (start == nums.length - 1) {    <- 這裡注意一下，這樣寫會讓 [0] 這種case fail，因為自己也要放啊！
    //     return;
    // }

    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        helper(nums, results, current, i + 1);
        current.remove(current.size() - 1);
    }
}

Java 的 List 用法需要瞭解一下： 參考

Follow up:

如果有重複元素怎麼辦？

我們可以這樣想：重複元素我們要先排序候選代表，我們prefer在前面的要先選才不會選到選過的

就是如果現在這個元素跟前面的一樣，又不是遞歸的開始代表不能選，因為前面的還沒被選過！

public void helper(int[] nums,
                       int startIndex,
                       List<Integer> subset,
                       List<List<Integer>> results) {
    results.add(new ArrayList<Integer>(subset));

    // i != startIndex represents it's not the first one
    // i == startIndex 表示為遞迴開始
    for (int i = startIndex; i < nums.length; i++) {
        if (i - 1 >= 0 && nums[i - 1] == nums[i] 
            && i != startIndex) {  
            continue;
        }

        subset.add(nums[i]);
        helper(nums, i + 1, subset, results);
        subset.remove(subset.size() - 1);
    }
}