LeetCode 78. Subsets 原创Java参考解答

问题描述

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

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路

题目是求一个数组的所有子集数组。该数组没有重复元素。

通过观察举例可以推断，题目的答案数量是2的N次方：2^N，N为原数组中元素个数。比如[1, 2, 3]就有8个子集。

答案个数是2^N的问题是NP问题，通常只能用搜索来解决。

我们可以在纸上或头脑中构建一棵深度优先搜索DFS递归树来分析。单独看递归树上任何一点，都是从该点出发在找该点的子集。[ ]就是向下找[ ]的所有子集，[1]就是向下找[1]的所有子集, [1, 2]就是向下找[1, 2]的所有子集……以此类推。

参考代码

把思路转为代码时候，我们可以先列出我们需要哪些参数：数组本身nums、当前集合subset、标记从哪个元素开始的startIndex和最终用来记录子集的results。题目本身函数只有一个参数，我们就需要自己用这四个参数构造一个递归辅助函数dfsHelper()。用自然语言来说，这个递归函数的定义就是：把所有以subset参数开头的集合都存到results里面。

拆解递归，dfsHelper()函数分以下几个步骤。

1. 把当前子集subset放入results
2. 把当前数组位置元素加入子集subset
3. 从当前子集已有元素的下一个元素位置开始调用自己dfsHelper()函数来找下一个位置的所有子集
4. 找完下一个位置的所有子集后，移除当前元素，去下一个位置元素

时间复杂度分析，递归函数时间复杂度可以套用公式分析：O(所有答案个数 * 构造每个答案的时间)。这道题有2^N个答案，每个答案时间为N，所以整个方法的时间复杂度为O(2^N * N)。

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return results;
        }
        
        List<Integer> subset = new ArrayList<>();
        dfsHelper(nums, 0, results, subset);

        return results;
    }
    
    private void dfsHelper(int[] nums, int startIndex, List<List<Integer>> results, List<Integer> subset) {
        // deep copy and add to results
        results.add(new ArrayList<>(subset));
        
        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            dfsHelper(nums, i + 1, results, subset);
            subset.remove(subset.size() - 1);
        }
    }
}

相关题目

LeetCode All in One 原创题目讲解汇总