78. 子集

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

解题思路

解法1：
1.很经典的回溯题型，给出的回溯算法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

2.在注释中，可以发现可以不写终止条件，因为本来我们就要遍历整颗树。有的同学可能担心不写终止条件会不会无限递归？并不会，因为每次递归的下一层就是从i+1开始的。

解题遇到的问题

无

后续需要总结学习的知识点

本题理解还不深刻，归根结底是对回溯算法不太了解，所以后续需要对回溯算法进行深入学习、总结

##解法1
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    LinkedList<Integer> path = new LinkedList<Integer>();
    List<List<Integer>> ansList = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ansList;
    }

    private void dfs(int i, int[] nums) {
        ansList.add(new ArrayList<Integer>(path));
        if (i >= nums.length) {
            return;
        }

        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(j + 1, nums);
            path.removeLast();
        }
    }
}