题目

image.png

思路

  • 思路一：可以直接从后遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集

  • 思路二：dfs+回溯

    代码

    ```java public List> subsets(int[] nums) {

    1.   List<List<Integer>> res = new ArrayList<>(); 
    2.   res.add(new ArrayList<>());
    3.   for (int i = 0; i < nums.length; i++) {
    4.       int size = res.size();
    5.       for (int j = 0; j < size; j++) {
    6.           List<Integer> list = new ArrayList<>(res.get(j));
    7.           list.add(nums[i]);
    8.           res.add(list);
    9.       }
    10.   }
    11.   return res;

    }

    //2.dfs + 回溯 public List> subsets(int[] nums) {

      List<List<Integer>> res = new ArrayList<>();
  backtrack(0, nums, res, new ArrayList<Integer>());
  return res;

    }

    private void backtrack(int i, int[] nums, List> res, ArrayList tmp) {

      res.add(new ArrayList<>(tmp));
  for (int j = i; j < nums.length; j++) {
      tmp.add(nums[j]);
      backtrack(j + 1, nums, res, tmp);
      tmp.remove(tmp.size() - 1);
  }

    }

``` 子集