首页 > 代码库 > Lintcode17 Subsets solution 题解
Lintcode17 Subsets solution 题解
【题目描述】
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.
给定一个含不同整数的集合,返回其所有的子集
注意:子集中的元素排列必须是非降序的,解集必须不包含重复的子集
【题目链接】
http://www.lintcode.com/en/problem/subsets/
【题目解析】
子集类问题类似Combination,以输入数组[1, 2, 3]分析,根据题意,最终返回结果中子集类的元素应该按照升序排列,故首先需要对原数组进行排序。题目的第二点要求是子集不能重复,至此原题即转化为数学中的组合问题。我们首先尝试使用 DFS 进行求解,大致步骤如下:
[1] -> [1, 2] -> [1, 2, 3]
[2] -> [2, 3]
[3]
将上述过程转化为代码即为对数组遍历,每一轮都保存之前的结果并将其依次加入到最终返回结果中。
【答案链接】
http://www.jiuzhang.com/solution/subsets/
Lintcode17 Subsets solution 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。