一起刷leetcode(78)：Subsets
地址：
https://oj.leetcode.com/problems/subsets/
题号：
78
题目：
Subsets
描述：
Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
4 个回复
MrFat
赞同来自: qq用户61090
递归实现，全部组合可以位从n个元素中选取0~n（subsets方法中的i）个元素。而从n个元素中选取m个元素，在选取某一个元素后，可以看做从后续元素中选取m-1个元素（递归主题方法思路）。
Java代码如下
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ret = new LinkedList<List<Integer>>();
List<List<Integer>> subret = new LinkedList<List<Integer>>();
for(int i = 0; i < nums.length+1; i++)
{
subret = getSubsets(nums,0,i);
ret.addAll(subret);
}
return ret;
}
public List<List<Integer>> getSubsets(int[] nums, int start, int length){
List<Integer> tempList = new LinkedList<Integer>();
List<List<Integer>> ret = new LinkedList<List<Integer>>();
List<List<Integer>> temp = new LinkedList<List<Integer>>();
if(length == 0)
{
ret.add(new LinkedList<Integer>());
return ret;
}
if(start + length > nums.length + 1 || nums.length == 0)
return ret;
for(int i = start; i < nums.length; ++i)
{
temp = getSubsets(nums, i+1, length-1);
if(ret != null){
for(List<Integer> list : temp){
List<Integer> tList = new LinkedList<Integer>();
tList.add(nums[i]);
tList.addAll(list);
ret.add(tList);
}
}
}
return ret;
}
}