LeetCode 78. Subsets(子集合)

时间:2021-07-06 12:11:26

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