LeetCode 78–subSets子集（Java）-集合遍历法

ゝ一纸荒年。 2023-06-20 14:55 2阅读 0赞

# [LeetCode –子集（Java）][LeetCode _Java] #

> 给定一组不同的整数S，返回所有可能的子集。

注意：1）子集中的元素必须按降序排列。2）解决方案集不得包含重复的子集。

例如，给定S = [1,2,3]，该方法将返回：
    [
      [3]，
      [1]，
      [2]，
      [1,2,3]，
      [1,3]，
      [2,3]，
      [1,2]，
      []
    ]

**思想**

给定n个不同整数的集合S，Sn和Sn-1之间存在关系。Sn-1的子集是\{Sn-1的子集\}与\{Sn-1中的每个元素+一个元素\}的并集。因此，可以快速将Java解决方案形式化。

**Java解决方案**

<table> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:top;"> <pre style="margin-left:0px;"><code>public ArrayList&lt;ArrayList&lt;Integer&gt;&gt; subsets(int[] S) {
	if (S == null)
		return null;
 
	Arrays.sort(S);
 
	ArrayList&lt;ArrayList&lt;Integer&gt;&gt; result = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt;();
 
	for (int i = 0; i &lt; S.length; i++) {
		ArrayList&lt;ArrayList&lt;Integer&gt;&gt; temp = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt;();
 
		//get sets that are already in result
		for (ArrayList&lt;Integer&gt; a : result) {
			temp.add(new ArrayList&lt;Integer&gt;(a));
		}
 
		//add S[i] to existing sets
		for (ArrayList&lt;Integer&gt; a : temp) {
			a.add(S[i]);
		}
 
		//add S[i] only as a set
		ArrayList&lt;Integer&gt; single = new ArrayList&lt;Integer&gt;();
		single.add(S[i]);
		temp.add(single);
 
		result.addAll(temp);
	}
 
	//add empty set
	result.add(new ArrayList&lt;Integer&gt;());
 
	return result;
}</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

### **相关文章：** ###

1.  [LeetCode –二进制监视（Java）][LeetCode _Java 1]
2.  [LeetCode –最大的可分割子集（Java）][LeetCode _Java 2]
3.  [LeetCode –子集II（Java）][LeetCode _II_Java]
4.  [LeetCode –排列（Java）][LeetCode _Java 3]

[LeetCode _Java]: https://www.programcreek.com/2013/01/leetcode-subsets-java/
[LeetCode _Java 1]: https://www.programcreek.com/2014/09/leetcode-binary-watch-java/
[LeetCode _Java 2]: https://www.programcreek.com/2014/08/leetcode-largest-divisible-subset-java/
[LeetCode _II_Java]: https://www.programcreek.com/2013/01/leetcode-subsets-ii-java/
[LeetCode _Java 3]: https://www.programcreek.com/2013/02/leetcode-permutations-java/