LintCode 17. Subsets 原创Java参考解答

问题描述

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

[
  [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)。

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 原创题目讲解汇总