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()函数分以下几个步骤。
- 把当前子集subset放入results
- 把当前数组位置元素加入子集subset
- 从当前子集已有元素的下一个元素位置开始调用自己dfsHelper()函数来找下一个位置的所有子集
- 找完下一个位置的所有子集后,移除当前元素,去下一个位置元素
时间复杂度分析,递归函数时间复杂度可以套用公式分析: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); } } }