LeetCode——Subsets

本文主要是介绍LeetCode——Subsets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.

• Example:
  Input: nums = [1,2,3]
  Output:
  [
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
  ]

解法——深度优先搜索

这道题其实和上一道题Combinations差不多，稍微改一下就能够拿来用了。

public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res=new ArrayList<List<Integer>>();for(int i=0;i<=nums.length;i++)combinecore(nums,i,0,res,new ArrayList<Integer>());return res;}private void combinecore(int[] nums, int k, int level, List<List<Integer>> res, ArrayList<Integer> out) {// TODO Auto-generated method stubif(out.size()==k){res.add(new ArrayList<Integer>(out));return;}for(int i=level;i<nums.length;i++){if(nums.length-i<(k-out.size()-1))return;out.add(nums[i]);combinecore(nums, k, i+1, res, out);out.remove(out.size()-1);}}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Subsets.
Memory Usage: 38.3 MB, less than 13.12% of Java online submissions for Subsets.

解法二——迭代

一定要记得深拷贝和浅拷贝的区别

public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res=new ArrayList<List<Integer>>();res.add(new ArrayList<Integer>());for(int i=0;i<nums.length;i++){int size=res.size();for(int j=0;j<size;j++){List<Integer> newres=new ArrayList<Integer>(res.get(j));newres.add(nums[i]);res.add(newres);}}return res;}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Subsets.
Memory Usage: 38.3 MB, less than 13.23% of Java online submissions for Subsets.

这篇关于LeetCode——Subsets的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---