078.子集

题目描述（中等难度）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

  解法一 拓展法

  思路:

  可以从条件上入手，先只考虑给定数组的 1 个元素的所有子数组，然后再考虑数组的 2 个元素的所有子数组 … 最后再考虑数组的 n 个元素的所有子数组。求 k 个元素的所有子数组，只需要在 k – 1 个元素的所有子数组里边加上 nums [ k ] 即可。

解法二 回溯法

解法三 DFS(深度优先算法)

/**
* 法III:DFS深度优先:一条路走到黑，不撞南墙不回头
*/
    public List<List<Integer>> subsets3(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums,result,0,new ArrayList<>());
        return result;
    }
/**
 * @param nums：要遍历的数组(题目给出)
 * @param result:结果集,每一次循环得到一个结果加到结果集
 * @param index:开始的索引，从nums的哪一个索引开始遍历
 * @param subset:形成的子集，这个子集要加到结果集里去
 */
private void dfs(int[] nums, List<List<Integer>> result, int index, ArrayList<Object> subset) {
    //复制一份子集加到结果集，
    // 为什么不直接把子集加到结果集，避免引用传递
    result.add(new ArrayList(subset));
    //判断是否终止递归
    if (nums.length == index){
        return;
    }
    for (int i = index; i < nums.length; i++) {
        //把当前元素加到subset里
        subset.add(nums[i]);
        //index:i+1
        dfs(nums, result, i+1, subset);
        //删除
        subset.remove(subset.size()-1);
    }
}