首页 > 代码库 > [LeetCode][Java] Subsets

[LeetCode][Java] Subsets

题目:

Given a set of distinct integers, nums, 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 nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题意:

给定一个由不同数字组成的数组nums,返回这个数组中的全部的子集。

注意:
        1.子集中的元素必须是升序排列

        2.终于的结果中不能包括反复的子集。

算法分析:

       结合上一题《Combinations》的方法,将上一题作为子函数来使用。

 

AC代码:

<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution 
{
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) 
    {
        ArrayList<ArrayList<Integer>> fres = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> flist= new ArrayList<Integer>();
        Arrays.sort(nums);
        fres.add(flist);
        for(int i=1;i<=nums.length;i++)
        {
        	ArrayList<ArrayList<Integer>> sres = new ArrayList<ArrayList<Integer>>();
        	sres=combine(nums, i);
        	fres.addAll(sres);
        }
        return fres;
    }
    public static ArrayList<ArrayList<Integer>> combine(int nums[], int k)
    { 
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(nums.length<=0 || nums.length<k) 
         return res; 
        helper(nums,k,0,new ArrayList<Integer>(), res);
        return res;
    }
    private static void helper(int nums[], int k, int start, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res)
    { 
        if(item.size()==k) 
        { 
            res.add(new ArrayList<Integer>(item));
            return; 
        } 
        for(int i=start;i<nums.length;i++) // try each possibility number in current position 
        { 
            item.add(nums[i]); 
            helper(nums,k,i+1,item,res); // after selecting number for current position, process next position  
            item.remove(item.size()-1); // clear the current position to try next possible number  
        } 
    }
}</span>


[LeetCode][Java] Subsets