子集

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets

题目描述：

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

思路：

非常典型的递归题目,全量遍历即可。

一，深度遍历的时候在每一层都将元素添加到结果容器。

class Solution {
    public List<List<Integer>> listss = new ArrayList();
    public List<Integer> lists = new ArrayList();
    public List<List<Integer>> subsets(int[] nums) {
       dfs(0, nums);
       return listss;
    }
    public void dfs(int start, int[] nums) {
        listss.add(new ArrayList(lists));
        for (int i = start; i < nums.length; i++) {
            lists.add(nums[i]);
            dfs(i + 1, nums);
            lists.remove(lists.size() - 1);
        }
    }
}

二，用栈来代替递归

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
       List<List<Integer>> listss = new ArrayList<>();
            List<Integer> lists = new ArrayList<>();
            Stack<List<Integer>> stack = new Stack<>();
            stack.push(lists);
            listss.add(lists);
            for(int i = 0; i < nums.length; i++) {
                while(!stack.isEmpty()) {
                    List<Integer> list = stack.pop();
                    List<Integer> listTwo = new ArrayList<>(list);
                    listTwo.add(nums[i]);
                    listss.add(listTwo);
                }
                for(int j = 0; j < listss.size(); j++) {
                    stack.push(listss.get(j));
                }
            }
            return listss;
    }
}

三，双重for循环遍历

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> listss = new ArrayList<>();
        List<Integer> lists = new ArrayList<>();    
        listss.add(lists);
       
        for(int i = 0; i < nums.length; i++) {
            int length = listss.size();
            for(int j = 0; j < length; j++) {
                List<Integer> list = listss.get(j);
                List<Integer> listTwo = new ArrayList<>(list);
                listTwo.add(nums[i]);
                listss.add(listTwo);
            }
        }
        return listss;
    }
}