78. Subsets

https://leetcode.com/problems/subsets/description/

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Thoughts

返回由不同数字组成的数组的powerset。找所有=>DFS。DFS每步从剩下的元素中选择一个元素。设置当前选择范围的起始位置以避免重复选择之前的元素。

Code

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(pos, res, path):
            for i in range(pos, len(nums)):
                path.append(nums[i])
                dfs(i + 1, res, path)
                path.pop()
            res.append([i for i in path])
        dfs(0, res, [])
        return res
        

class Solution {
    private void helper(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            helper(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        helper(nums, 0, new ArrayList<>(), res);
        return res;
    }
}

Analysis

时间复杂度是指数级. 2^N. 每个元素可选择出现或不出现. 空间复杂度O(N).