Subsets

LeetCode LintCode

详细解说

这道题题目要求所有可能的子集。老师说过，碰到让你找所有方案的题，一定要用DFS.

回溯法的图示：
回溯法可用图示和函数运行的堆栈图来理解，强烈建议使用图形和递归的思想分析，以数组[1, 2, 3]进行分析。下图所示为list及resul t动态变化的过程，箭头向下表示list.add及result.add操作，箭头向下表示list.remove操作。
http://7xiys0.com1.z0.glb.clouddn.com/gitbook143117722134.jpg

// 递归：实现方式，一种实现DFS算法的一种方式
class Solution {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        if (nums == null) {
            return results;
        }
        if (nums.length == 0) {
            results.add(new ArrayList<Integer>());
            return results;
        }
        Arrays.sort(nums);
        helper(new ArrayList<Integer>(), nums, 0, results);
        return results;
    }
    // 递归三要素
    // 1. 递归的定义：在 Nums 中找到所有以 subset 开头的的集合，并放到 results
    private void helper(ArrayList<Integer> subset,
                        int[] nums,
                        int startIndex,
                        ArrayList<ArrayList<Integer>> results) {
        // 2. 递归的拆解
        // deep copy
        // results.add(subset);
        results.add(new ArrayList<Integer>(subset));
        for (int i = startIndex; i < nums.length; i++) {
            // [1] -> [1,2]
            subset.add(nums[i]);
            // 寻找所有以 [1,2] 开头的集合，并扔到 results
            helper(subset, nums, i + 1, results);
            // [1,2] -> [1]  回溯
            subset.remove(subset.size() - 1);
        }
        // 3. 递归的出口
        // return;
    }
}

以这个问题为例子，要好好训练自己找到递归三要素的能力：递归的定义，递归的拆解，递归的出口。比如本体中递归的定义，也就是helper method要做的事情，便是找到以传入参数subset开头的所有subsets,并且加入到results里面。

self explanation