Given a set of distinct integers, nums, return all possible subsets.
Note: 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],
[]
]
题目标签：Array
方法 1：
题目给了我们一个nums array，让我们找到所有的子集合。看到这种要找到所有的可能性的题目一般都要用到递归。我们设一个List List res，先把 [ ] 加入res。接着我们来根据原题中的例子来看一下。
[1, 2, 3]
我们依次把每一个数字的index，放到递归function 里去， 还要给一个 new ArrayList<>() 叫list 放到function 里。在递归function里，对于每一个index，首先把这个index 的数字加入list，然后把list 加入res 里。接着遍历它之后的所有数字，对于每一个数字，建立一个新的new ArrayList<>() 把这个list的值存入新的，继续递归下去。直到拿到的index 已经是最后一个数字了，把自己加入list，把list 加入res之后，直接跳过遍历，因为后面没有数字了，就返回了。我们来看一下例子
[1] [2] [3]
/ \ / \
[1,2] [1,3] [2,3]
/
[1,2,3]
顺序为[ [ ], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]
Java Solution 1:
Runtime beats 23.24%
完成日期：07/24/2017
关键词：Array
关键点：递归
public class Solution
{
List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums)
{
List<Integer> empty = new ArrayList<>();
res.add(empty); if(nums == null || nums.length == 0)
return res; // sort nums array
Arrays.sort(nums); // pass each number into findSubset
for(int i=0; i<nums.length; i++)
findSubset(i, nums, new ArrayList<>()); return res;
} public void findSubset(int begin, int[] nums, List<Integer> list)
{
// add nums[begin] into list
list.add(nums[begin]); // add this list into res
res.add(list); // pass rest numbers to findSubset with list starting from [begin...
for(int i=begin+1; i<nums.length; i++)
{
List<Integer> temp = new ArrayList<>();
temp.addAll(list); findSubset(i, nums, temp);
} return;
}
}
参考资料：N/A
方法 2：
基本的原理和方法1一样，只不过在方法2中，可以利用list 的remove 把最后一个数字去除，然后继续与剩下的数字组成subset。这样的话就可以不需要在subsets function里利用for loop把每一个数字pass 给helper function了。方法 2 更加清晰简介，具体看code。
Java Solution 2:
Runtime beats 23.24%
完成日期：08/25/2017
关键词：Array
关键点：递归，当新的递归返回的时候把tmpRes list里的最后一个数字去除
public class Solution
{
public List<List<Integer>> subsets(int[] nums)
{
// sort nums array
Arrays.sort(nums);
// create res
List<List<Integer>> res = new ArrayList<>();
// call recursion function
helper(res, new ArrayList<>(), 0, nums); return res;
} public void helper(List<List<Integer>> res, List<Integer> tmpRes, int pos, int[] nums)
{
// here should be <= not just < because we need to add the new tmpRes in next recursion.
// Therefore, we need one more bound to add tmpRes
if(pos <= nums.length)
res.add(new ArrayList<>(tmpRes)); // once the new recursion is finished, remove the last number in the tmpRes and continue to
// add rest numbers to get new subsets
for(int i=pos; i<nums.length; i++)
{
tmpRes.add(nums[i]);
helper(res, tmpRes, i+1, nums);
tmpRes.remove(tmpRes.size()-1);
}
}
}
参考资料：
https://discuss.leetcode.com/topic/22638/very-simple-and-fast-java-solution/4
LeetCode 算法题目列表 - LeetCode Algorithms Questions List