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

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

    示例:

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

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/power-set-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    1. package BackTrack;
    3. import java.util.ArrayList;
    4. import java.util.List;
    6. public class PowerSetLCCI {
    7.     public static void main(String[] args) {
    8.         int[] test = {1,2,6};
    9.         for(List<Integer> element:method2(test)){
    10.             System.out.println(element);
    11.         }
    12.     }
    14.     //法一：非递归解决
    15.     public static List<List<Integer>> method1(int[] nums){
    16.         List<List<Integer>> res = new ArrayList<>();
    17.         res.add(new ArrayList<>(){});
    18.         for(int num:nums){
    19.             //(int i=0;i<res.size();i++)这种写法会报错，因为res.size()会不断发生变化
    20.             for(int i = 0, j = res.size(); i < j; i++){
    21.                 List<Integer> list = new ArrayList<>(res.get(i));
    22.                 list.add(num);
    23.                 res.add(list);
    24.             }
    25.         }
    26.         return res;
    27.     }
    29.     //法二：递归解决
    30.     public static List<List<Integer>> method2(int[] nums){
    31.         List<List<Integer>> res = new ArrayList<>(1 << nums.length);
    32.         res.add(new ArrayList<>());
    33.         recursion(nums, 0, res);
    34.         return res;
    35.         }
    37.     public static void recursion(int[] nums, int index, List<List<Integer>> res) {
    38.         //数组中的元素都访问完了，直接return
    39.         if (index >= nums.length)
    40.             return;
    41.         int size = res.size();
    42.         for (int j = 0; j < size; j++) {
    43.             List<Integer> list = new ArrayList<>(res.get(j));
    44.             //然后在新的子集后面追加一个值
    45.             list.add(nums[index]);
    46.             res.add(list);
    47.         }
    48.         //递归下一个元素
    49.         recursion(nums, index + 1, res);
    50.     }
    52.     //回溯
    53.     public List<List<Integer>> subsets(int[] nums) {
    54.         //存放结果
    55.         List<List<Integer>> list = new ArrayList<>();
    56.         //开始递归
    57.         backtrack(list, new ArrayList<>(), nums, 0);
    58.         return list;
    59.     }
    61.     private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
    62.         //走过的所有路径都是子集的一部分，所以都要加入到集合中
    63.         list.add(new ArrayList<>(tempList));
    64.         //从第start哥元素开始
    65.         for (int i = start; i < nums.length; i++) {
    66.             //做出选择
    67.             tempList.add(nums[i]);
    68.             //递归
    69.             backtrack(list, tempList, nums, i + 1);
    70.             //撤销选择
    71.             tempList.remove(tempList.size() - 1);
    72.         }
    73.     }
    74. }