本文共 2859 字，大约阅读时间需要 9 分钟。
原题链接：
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 > subsets(int[] array) { List > result = new ArrayList >(); //如果数组长度为0，则返回结果 if (array.length == 0) { return result; } //数组元素排序 Arrays.sort(array); //dfs搜索 dfs(array, 0, new ArrayList (), result); return result; } /* * dfs搜索算法 * */ public void dfs(int[] array, int index, List path, List > result) { result.add(new ArrayList (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 stub int[] array= { 1,4,11,9}; SubsetsDemo sd=new SubsetsDemo(); List > list=sd.subsets(array); Iterator > itx = list.iterator(); while (itx.hasNext()) { List 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 > subsets (int[] array) { if (array == null) return null; //对数组进行排序 Arrays.sort (array); List > result = new ArrayList > (); //调用dfs算法 result = dfs (array, array.length - 1); result.add (new ArrayList ()); return result; } /* * 算法设计 * 1. 从数组的最后一个元素开始，下标为array.length-1，对每一个元素进行递归调用，index-1 * 2. 获得子集Subset(n)= Subset(n-1)+(n itself) +(add n to Subset(n-1)) * 3. 最后加上空集 [] * */ List > dfs (int[] array, int index) { List > result = new ArrayList > (); if (index < 0) { return result; } List > subResult = dfs (array, index - 1); result.addAll (subResult); for (int i = 0; i < subResult.size (); i++) { List 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 stub int[] array= { 1,4,11,9}; SubsetsDemo2 sd=new SubsetsDemo2(); List > list=sd.subsets(array); Iterator > itx = list.iterator(); while (itx.hasNext()) { List sublist = itx.next(); System.out.println(sublist); } }}
（完）
转载地址：http://zztdi.baihongyu.com/