LintCode 17. Subsets 原创Java参考解答

LintCode 17. Subsets 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/subsets/

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

Notice
  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

Example

If S = [1,2,3], a solution is:

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

解题思路

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

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

答案个数是2N的问题是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(所有答案个数 * 构造每个答案的时间)。这道题有2N个答案,每个答案时间为N,所以整个方法的时间复杂度为O(2N * N)。

class Solution { 
    /** 
     * @param S: A set of numbers. 
     * @return: A list of lists. All valid subsets. 
     */ 
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) { 
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); 
        if (nums == null || nums.length == 0) { 
            return results; 
        } 
        Arrays.sort(nums); 
        ArrayList<Integer> subset = new ArrayList<Integer>(); 
        dfsHelper(nums, 0, subset, results); 
        return results; 
    } 
     
    private void dfsHelper(int[] nums, int startIndex, ArrayList<Integer> subset, ArrayList<ArrayList<Integer>> results) { 
        // 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, subset, results); 
            subset.remove(subset.size() - 1); 
        } 
    } 
}

相关题目

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

发表回复

您的电子邮箱地址不会被公开。