[补档 12th Jan] 子集

[补档 12th Jan] 78 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

  	//初始化一个结果集合
    List<List<Integer>> res = new ArrayList<List<Integer>>();
  	//设置flags 看看是否重复
    boolean[] flags;
    public List<List<Integer>> subsets(int[] nums) {
        //得到数组的长度
        int nums_len = nums.length;
        //初始化子集
        LinkedList<Integer> track = new LinkedList<Integer>(); 
        //设置flags数组的长度
        flags = new boolean[nums_len];
        // 回溯 分别是 整数数组 起始位置下标 整数数组长度 和 初始化的子集
        backtrack(nums, 0, nums_len, track);
        return res;
    }

    // 回溯函数参数 分别是 整数数组 起始下标 整数数组长度 子集
    public void backtrack(int[] nums, int start, int len, LinkedList<Integer> track){
        //在集合中添加一个子集 这里用的是深拷贝 深拷贝就是在饮用类型成员变量时 为了引用类型的数据成员另外开辟了一个独立的内存空间 实现了真正内容上的拷贝
        res.add(new ArrayList(track));
        //取出整数数组中的元素
        for(int i = start; i < len; i++ ){
          //如果这个数没有被使用过  
          if(!flags[i]){
                //标识这个数被使用
                flags[i] = true;
                //添加到子集的最后一位中
                track.addLast(nums[i]);
            		//在进行回溯 以该数的后一位为起始位 长度仍然为整数数组的长度
            		//子集仍然为track 不过是另一个对象
                backtrack(nums, i+1, len, track);
            		//去除子集中最后一个元素
                track.removeLast();
            		//置为false 表示这个数在之后求子集的时候还可以使用
                flags[i] = false;
            }
        }
    }
}

该解法参考labuladongC++版