[LeetCode] 78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:
Input: nums = [0]
Output: [[],[0]]

Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

子集。

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

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

思路

思路还是回溯，而且模板要背下来。第八行的 sort 被省略是因为 78 题没有重复元素，然后之后的 90 题有重复元素，这一行排序就用得上了。递归函数的一开始，将子数组加入结果集，然后遍历 input，注意遍历的时候不是从 0 开始，而是从 start index 开始。

复杂度

时间O(n * 2^n) - 因为最后就是有 2^n 个结果，每次进入 helper 函数的时候 list 都会被复制一次
空间O(n * 2^n)

代码

Java实现

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // corner case
        if (nums == null || nums.length == 0) {
            return res;
        }
        // Arrays.sort(nums);
        helper(res, new ArrayList<>(), nums, 0);
        return res;
    }

    private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, int start) {
        res.add(new ArrayList<>(list));
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            helper(res, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }
}