Subsets

几乎所有的搜索问题都可以以这个代码为模板

Leetcode https://leetcode.cn/problems/subsets/

题目描述

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

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

示例 1：

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

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

示例 2：

输入：nums = [0] 输出：[ [], [0] ]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

解题报告

这道题在 Leetcode 提交的时候，深搜会更快一点。。。

• 深度优先搜索 DFS

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();

        if (nums == null) {
            return results;
        }

        if (nums.length == 0) {
            results.add(new ArrayList<Integer>());
            return results;
        }

        Arrays.sort(nums);
        helper(new ArrayList<Integer>(), nums, 0, results);

        return results;
    } // end subsets

    private void helper(ArrayList<Integer> subset, int[] nums, int startIndext, List<List<Integer>> results) {
        results.add(new ArrayList<Integer>(subset));
        for (int i = startIndext; i < nums.length; i++) {
            subset.add(nums[i]);
            helper(subset, nums, i + 1, results);
            subset.remove(subset.size() - 1);
        } // end for i
    } // end helper
} // end Solution

• 宽度优先搜索 BFS

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> queue = new ArrayList<>();
        int index = 0;

        Arrays.sort(nums);
        queue.add(new ArrayList<Integer>());
        while (index < queue.size()) {
            List<Integer> subset = queue.get(index++);
            for (int i = 0; i < nums.length; i++) {
                if (subset.size() != 0 && subset.get(subset.size() - 1) >= nums[i]) {
                    continue;
                }
                List<Integer> newSubset = new ArrayList<>(subset);
                newSubset.add(nums[i]);
                queue.add(newSubset);
            } // end for i
        } // end while loop

        return queue;
    } // end subsets
} // end Solution