February 10, 2019

78. Subsets

法一 DFS Backtracking

视频：https://www.youtube.com/watch?v=VdnvmfzA1pw

Time O(2^n) Space O(n)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }
        List<Integer> cur = new ArrayList<>();
        // 把所有以 [] 开头的集合都找到，并扔到 results 里
        helper(nums, 0, cur, res);
        return res;
    }

    // 把所有以 subset 开头的集合都找到，并扔到 results 里
    private void helper(int[] nums, int index, List<Integer> cur, List<List<Integer>> res) {
        // Add subset - Each subset we visit will be added to the results.
        // deep copy 
        res.add(new ArrayList<>(cur));
        for (int i = index; i < nums.length; i++) {
            // 尝试寻找 subset + [nums[i]] 开头的所有的子集
            cur.add(nums[i]);
            helper(nums, i + 1, cur, res);
            // 回溯
            cur.remove(cur.size() - 1);
        }
    }
}

class Solution:
    def subsets(self, nums: 'List[int]') -> 'List[List[int]]':
        res = []
        self.helper(nums, 0, [], res)
        return res
    
    def helper(self, nums, index, cur, res):
        res.append(cur)
        for i in range(index, len(nums)):
            self.helper(nums, i + 1, cur + [nums[i]], res)

法二

对 input = {1, 2, 3} 来说，递归树的每一层都有加1不加1，加2不加2，加3不加3两个选择。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        if (nums == null) {
            return res;
        }
        List<Integer> cur = new LinkedList<>();
        dfsHelper(nums, 0, cur, res);
        return res;
    }
    
    private void dfsHelper(int[] nums, int index, List<Integer> cur, List<List<Integer>> res) {
        
        // base case
        if (index == nums.length) {
            res.add(new ArrayList<>(cur)); // 这里要注意加new ArrayList<>(cur)
            return;
        }
        
        dfsHelper(nums, index + 1, cur, res);
        
        cur.add(nums[index]);
        dfsHelper(nums, index + 1, cur, res);
        cur.remove(cur.size() - 1); // 这里特别注意remove的方法
    
    }
}

class Solution:
    def subsets(self, nums: 'List[int]') -> 'List[List[int]]':
        res= []
        self.helper(0, nums, [], res)
        return res
    
    def helper(self, index, nums, cur, res):
        if index == len(nums):
            res.append(cur)
            return
        self.helper(index + 1, nums, cur + [], res)
        self.helper(index + 1, nums, cur + [nums[index]], res)

时间复杂度：O(2^n)，空间复杂度：O(n)