回溯法理解-2

1.leetcode面试题08.04幂集

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

 解题思路：

1.构建出符合题目解的n叉树，即可根据树来设定结束回溯的条件，剪枝的条件，已经是否需要辅助数组 

通过给出的关于解空间的n叉树，可以知道，需要在回溯的时候传递当前遍历在nums中的index，向下延伸的时候只需要找当前index后面的数，而不需要考虑前面的数，（如果在需要考虑前面的数的情况，可以使用一个boolean[] used数组来辅助）；同时观察解空间树中从根到任意节点组成的list都是一个可行解；还有可以看出因为后一个数总是从index后面开始遍历来的，所以算是直接剪枝了；（后面所有的关于回溯法的问题都可以根据思路来写）

回溯法的总结：
1.根据题目写出解空间树

2.写出前序优先遍历该树所需要的参数，参数都是根据合何时不需要向下生成孩子节点，即树的边界，以及怎么根据给出的nums数组来遍历这个解空间树

3.一定要考虑是否可以剪枝，剪枝可以节省大量的时间复杂度

 代码：

class Solution {
public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> reList = new ArrayList<>();
        if(nums == null || nums.length == 0 )return reList;
        List<Integer> curList = new ArrayList<>();
        int len = nums.length;
        dfs(reList,curList,0,0,nums,len);
        return reList;
    }


    public void dfs(List<List<Integer>> reList,List<Integer> curList,int depth,int index,int[] nums,int len){
        if(index == len){
            reList.add(new ArrayList<>(curList));
            return;
        }
        reList.add(new ArrayList<>(curList));
        for (int i = index; i < len; i++) {
            curList.add(nums[i]);
            dfs(reList,curList,i+1,i+1,nums,len);
            curList.remove(curList.size() -1);
        }


    }

}