首页 > 代码库 > LeetCode: Subsets 解题报告

LeetCode: Subsets 解题报告

2024-10-29 04:53:02   210人阅读

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],

  []

]

SOLUTION 1:

使用九章算法的模板：

递归解决。

1. 先对数组进行排序。

2. 在set中依次取一个数字出来即可，因为我们保持升序，所以不需要取当前Index之前的数字。

技术分享
 1 public class Solution { 2     public List<List<Integer>> subsets(int[] S) { 3         List<List<Integer>> ret = new ArrayList<List<Integer>>(); 4         if (S == null) { 5             return ret; 6         } 7          8         Arrays.sort(S); 9         10         dfs(S, 0, new ArrayList<Integer> (), ret);11         12         return ret;13     }14     15     public void dfs(int[] S, int index, List<Integer> path, List<List<Integer>> ret) {16         ret.add(new ArrayList<Integer>(path));17         18         for (int i = index; i < S.length; i++) {19             path.add(S[i]);20             dfs(S, i + 1, path, ret);21             path.remove(path.size() - 1);22         }23     }24 }
View Code

 

SOLUTION 2:

相当牛逼的bit解法。基本的想法是，用bit位来表示这一位的number要不要取，第一位有1，0即取和不取2种可能性。所以只要把0到N种可能

都用bit位表示，再把它转化为数字集合，就可以了。

Ref: http://www.fusu.us/2013/07/the-subsets-problem.html

There are many variations of this problem, I will stay on the general problem of finding all subsets of a set. For example if our set is [1, 2, 3] - we would have 8 (2 to the power of 3) subsets: {[], [1], [2], [3], [1, 2], [1, 3], [1, 2, 3], [2, 3]}. So basically our algorithm can‘t be faster than O(2^n) since we need to go through all possible combinations.

 

There‘s a few ways of doing this. I‘ll mention two ways here - the recursive way, that we‘ve been taught in high schools; and using a bit string.

 

Using a bit string involves some bit manipulation but the final code can be found easy to understand. The idea  is that all the numbers from 0 to 2^n are represented by unique bit strings of n bit width that can be translated into a subset. So for example in the above mentioned array we would have 8 numbers from 0 to 7 inclusive that would have a bit representation that is translated using the bit index as the index of the array.

 

Nr

Bits

Combination

0

000

{}

1

001

{1}

2

010

{2}

3

011

{1, 2}

4

100

{3}

5

101

{1, 3}

6

110

{2, 3}

7

111

{1, 2, 3}

技术分享
 1 public class Solution { 2     public List<List<Integer>> subsets(int[] S) { 3         List<List<Integer>> ret = new ArrayList<List<Integer>>(); 4         if (S == null || S.length == 0) { 5             return ret; 6         } 7          8         int len = S.length; 9         Arrays.sort(S);10         11         // forget to add (long).12         long numOfSet = (long)Math.pow(2, len);13         14         for (int i = 0; i < numOfSet; i++) {15             // bug 3: should use tmp - i.16             long tmp = i;17             18             ArrayList<Integer> list = new ArrayList<Integer>();19             while (tmp != 0) {20                 // bug 2: use error NumberOfTrailingZeros. 21                 int indexOfLast1 = Long.numberOfTrailingZeros(tmp);22                 list.add(S[indexOfLast1]);23                 24                 // clear the bit.25                 tmp ^= (1 << indexOfLast1);26             }27             28             ret.add(list);29         }30         31         return ret;32     }33     34 }
View Code

 

GITHUB: https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dfs/Subsets.java

LeetCode: Subsets 解题报告


联系
我们