LeetCode刷题：78. Subsets

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

LeetCode刷题：78. Subsets

原题链接：https://leetcode.com/problems/subsets/description/

Given a set of distinct integers, nums, return all possible subsets (the power set).

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

这个题目的意思是给定一个集合，集合中的整数互不重复。要求返回所有可能的子集。
注意：空集也是一个子集。子集中的元素也必须互不重复。

问题分析

采用DFS算法求解。

算法设计

package com.bean.algorithmbasic;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;public class SubsetsDemo {public List<List<Integer>> subsets(int[] array) {List<List<Integer>> result = new ArrayList<List<Integer>>();//如果数组长度为0，则返回结果if (array.length == 0) {return result;}//数组元素排序Arrays.sort(array);//dfs搜索dfs(array, 0, new ArrayList<Integer>(), result);return result;}/** dfs搜索算法* */public void dfs(int[] array, int index, List<Integer> path, List<List<Integer>> result) {result.add(new ArrayList<Integer>(path));for (int i = index; i < array.length; i++) {path.add(array[i]);dfs(array, i + 1, path, result);path.remove(path.size() - 1);}}public static void main(String[] args) {// TODO Auto-generated method stubint[] array= {1,4,11,9};SubsetsDemo sd=new SubsetsDemo();List<List<Integer>> list=sd.subsets(array);Iterator<List<Integer>> itx = list.iterator();while (itx.hasNext()) {List<Integer> sublist = itx.next();System.out.println(sublist);}}}

运行结果：

[1]
[1, 4]
[4]
[1, 9]
[1, 4, 9]
[4, 9]
[9]
[1, 11]
[1, 4, 11]
[4, 11]
[1, 9, 11]
[1, 4, 9, 11]
[4, 9, 11]
[9, 11]
[11]
[]

另一种写法

package com.bean.algorithmbasic;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;public class SubsetsDemo2 {public List <List <Integer>> subsets (int[] array) {if (array == null)return null;//对数组进行排序Arrays.sort (array);List <List <Integer>> result = new ArrayList <List <Integer>> ();//调用dfs算法result = dfs (array, array.length - 1);result.add (new ArrayList <Integer> ());return result;}/** 算法设计* 1. 从数组的最后一个元素开始，下标为array.length-1，对每一个元素进行递归调用，index-1* 2. 获得子集Subset(n)= Subset(n-1)+(n itself) +(add n to Subset(n-1))* 3. 最后加上空集 []* */List <List <Integer>> dfs (int[] array, int index) {List <List <Integer>> result = new ArrayList <List <Integer>> ();if (index < 0) {return result;}List <List <Integer>> subResult = dfs (array, index - 1);result.addAll (subResult);for (int i = 0; i < subResult.size (); i++) {List <Integer> bList = new ArrayList <> ();bList.addAll (subResult.get (i));bList.add (array[index]);result.add (bList);}result.add (Arrays.asList (array[index]));return result;}public static void main(String[] args) {// TODO Auto-generated method stubint[] array= {1,4,11,9};SubsetsDemo2 sd=new SubsetsDemo2();List<List<Integer>> list=sd.subsets(array);Iterator<List<Integer>> itx = list.iterator();while (itx.hasNext()) {List<Integer> sublist = itx.next();System.out.println(sublist);}}}

（完）

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

---