一起刷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],
[]
]
已邀请:

MrFat

赞同来自:


递归实现,全部组合可以位从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;
    }
}

要回复问题请先登录注册

返回顶部