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:

解题思路

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

通过观察举例可以推断,题目的答案数量是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)。

相关题目

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注