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);


    }


}

原文地址：https://blog.csdn.net/sinat_32502451/article/details/142702625

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！