LeetCode78 子集

题目：

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

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

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

思路：

• 回溯法
• 选择数组元素，如果数组元素全都选择完了，就添加到结果集里面
• 回溯移除最后添加的数组元素，移除后再次进行递归添加新的子集

代码：

class LeetCode78 {//存放结果集List<List<Integer>> resultList = new ArrayList<>();//存放已经被选中的数据List<Integer> list = new ArrayList<>();    public List<List<Integer>> subsets(int[] nums) {//回溯法 dfs (0, nums);return resultList;}public void dfs (int cur, int[] nums) {//如果全都选择完了，就添加到结果集里面if (cur == nums.length) {resultList.add(new ArrayList<Integer>(list));return;}//选择数组元素list.add( nums[cur]);//递归dfs(cur+1, nums);//回溯，移除刚添加的(也就是最后一个)元素，以便后面再重新选择list.remove( list.size()-1);// 移除后一个元素后,再次进行递归添加新的子集到list中dfs(cur+1, nums);}}