计算一组数字的所有子集

我想find一组整数的子集。 它是具有回溯的“子集和”algorithm的第一步。 我写了下面的代码，但它没有返回正确的答案：

码：

BTSum(0, nums); ///************** ArrayList<Integer> list = new ArrayList<Integer>(); public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) { if (n == numbers.size()) { for (Integer integer : list) { System.out.print(integer+", "); } System.out.println("********************"); list.removeAll(list); System.out.println(); } else { for (int i = n; i < numbers.size(); i++) { if (i == numbers.size() - 1) { list.add(numbers.get(i)); BTSum(i + 1, numbers); } else { list.add(numbers.get(i)); for (int j = i+1; j < numbers.size(); j++) BTSum(j, numbers); } } } return null; } 

例如，如果我想要计算set = {1,3,5}的子集我的方法的结果是：

  1, 3, 5, ******************** 5, ******************** 3, 5, ******************** 5, ******************** 3, 5, ******************** 5, ******************** 

我想要它产生

 1, 3, 5 1, 5 3, 5 5 

我认为问题是从部分list.removeAll（列表）; 但我不知道如何纠正它。

Answer 1

你想要的是一个Powerset 。 这是一个简单的实现：

 public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) { Set<Set<Integer>> sets = new HashSet<Set<Integer>>(); if (originalSet.isEmpty()) { sets.add(new HashSet<Integer>()); return sets; } List<Integer> list = new ArrayList<Integer>(originalSet); Integer head = list.get(0); Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size())); for (Set<Integer> set : powerSet(rest)) { Set<Integer> newSet = new HashSet<Integer>(); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); } return sets; } 

我会给你一个例子来解释algorithm如何为{1, 2, 3}的权力集合起作用：

• 删除{1} ，然后为{2, 3}执行powerset;
  • 删除{2} ，并为{3}执行powerset;
    • 删除{3} ，并为{}执行powerset;
      • {} Powerset是{{}} ;
    • {3} Powerset与{{}} = { {}, {3} }结合使用{ {}, {3} } ;
  • {2, 3} Powerset与{ {}, {3} } = { {}, {3}, {2}, {2, 3} }
• {1, 2, 3} Powerset与{ {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} } 。

Answer 2

只是一个初步的如何你可以解决这个问题：

方法1

• 采取您的号码列表中的第一个元素
• 从剩余的号码列表（即没有select的号码列表）生成所有的子集=>recursion！
• 对于在上一步中find的每个子集，将子集本身和与在步骤1中select的元素连接的子集添加到输出中。

当然，你必须检查基本情况，即如果你的号码列表是空的。

方法2

众所周知的事实是，具有n元素的集合具有2^n个子集。 因此，可以从0到2^n的二进制数进行计数，并将二进制数解释为相应的子集。 请注意，这种方法需要一个具有足够数字的二进制数来表示整个集合。

将两种方法中的一种转换为代码应该不是一个太大的问题。

Answer 3

你的代码真的很混乱，没有解释。

你可以迭代地用一个掩码来确定哪些数字在集合中。 例如，从0到2 ^ n的每个数字在其二进制表示中给出唯一的子集

对于n = 3：

i = 5 – > 101二进制，在二进制中select第一个和最后一个元素i = 7 – > 111，select前三个元素

假设有n个元素（n <64，毕竟，如果n大于64，你将永远运行）。

 for(long i = 0; i < (1<<n); i++){ ArrayList<Integer> subset = new ArrayList<Integer>(); for(int j = 0; j < n; j++){ if((i>>j) & 1) == 1){ // bit j is on subset.add(numbers.get(j)); } } // print subset } 

Answer 4

考虑一个Noob访问者（感谢谷歌）这个问题 – 像我一样
这是一个简单的主要工作的recursion解决scheme：

Set = {a，b，c，d，e}
那么我们可以把它Subset of {b,c,d,e} {a} + Subset of {b,c,d,e}

 public class Powerset{ String str = "abcd"; //our string public static void main(String []args){ Powerset ps = new Powerset(); for(int i = 0; i< ps.str.length();i++){ //traverse through all characters ps.subs("",i); } } void subs(String substr,int index) { String s = ""+str.charAt(index); //very important, create a variable on each stack s = substr+s; //append the subset so far System.out.println(s); //print for(int i=index+1;i<str.length();i++) subs(s,i); //call recursively } } 

OUTPUT

 a ab abc abcd abd ac acd ad b bc bcd bd c cd d 

Answer 5

很明显，任何给定集合的子集总数等于2 ^（集合中元素的数量）。 如果设置

A = {1，2，3}

那么A的子集是：

{}，{1}，{2}，{3}，{1,2}，{1,3}，{2,3}，{1,2,3}

如果我们看它就像二进制数字。

{000}，{001}，{010}，{011}，{100}，{101}，{110}，{111}

如果我们考虑以上：

 static void subSet(char[] set) { int c = set.length; for (int i = 0; i < (1 << c); i++) { System.out.print("{"); for (int j = 0; j < c; j++) { if ((i & (1 << j)) > 0) { System.out.print(set[j] + " "); } } System.out.println("}"); } } public static void main(String[] args) { char c[] = {'a', 'b', 'c'}; subSet(c); } 

Answer 6

 private static void findSubsets(int array[]) { int numOfSubsets = 1 << array.length; for(int i = 0; i < numOfSubsets; i++) { int pos = array.length - 1; int bitmask = i; System.out.print("{"); while(bitmask > 0) { if((bitmask & 1) == 1) System.out.print(array[pos]+","); bitmask >>= 1; pos--; } System.out.print("}"); } } 

Answer 7

基于我今天学到的，这里是Java解决scheme它是基于recursion

 public class Powerset { public static void main(String[] args) { final List<List<String>> allSubsets = powerSet(Arrays.asList(1, 2, 3, 4), 0); for (List<String> subsets : allSubsets) { System.out.println(subsets); } } private static List<List<String>> powerSet(final List<Integer> values, int index) { if (index == values.size()) { return new ArrayList<>(); } int val = values.get(index); List<List<String>> subset = powerSet(values, index + 1); List<List<String>> returnList = new ArrayList<>(); returnList.add(Arrays.asList(String.valueOf(val))); returnList.addAll(subset); for (final List<String> subsetValues : subset) { for (final String subsetValue : subsetValues) { returnList.add(Arrays.asList(val + "," + subsetValue)); } } return returnList; } } 

运行它将会给出结果

 [1] [2] [3] [4] [3,4] [2,3] [2,4] [2,3,4] [1,2] [1,3] [1,4] [1,3,4] [1,2,3] [1,2,4] [1,2,3,4] 

Answer 8

我实际上是试图解决这个问题，并得到了前一篇文章中的algorithm@phimuemue。这是我实现的。 希望这个作品。

 /** *@Sherin Syriac * */ import java.util.ArrayList; import java.util.List; public class SubSet { ArrayList<List<Integer>> allSubset = new ArrayList<List<Integer>>(); /** * @param args */ public static void main(String[] args) { SubSet subSet = new SubSet(); ArrayList<Integer> set = new ArrayList<Integer>(); set.add(1); set.add(2); set.add(3); set.add(4); subSet.getSubSet(set, 0); for (List<Integer> list : subSet.allSubset) { System.out.print("{"); for (Integer element : list) { System.out.print(element); } System.out.println("}"); } } public void getSubSet(ArrayList<Integer> set, int index) { if (set.size() == index) { ArrayList<Integer> temp = new ArrayList<Integer>(); allSubset.add(temp); } else { getSubSet(set, index + 1); ArrayList<List<Integer>> tempAllSubsets = new ArrayList<List<Integer>>(); for (List subset : allSubset) { ArrayList<Integer> newList = new ArrayList<Integer>(); newList.addAll(subset); newList.add(set.get(index)); tempAllSubsets.add(newList); } allSubset.addAll(tempAllSubsets); } } } 

Answer 9

 // subsets for the set of 5,9,8 import java.util.ArrayList; import java.util.List; public class Subset { public static void main(String[] args) { List<Integer> s = new ArrayList<Integer>(); s.add(9); s.add(5); s.add(8); int setSize = s.size(); int finalValue = (int) (Math.pow(2, setSize)); String bValue = ""; for (int i = 0; i < finalValue; i++) { bValue = Integer.toBinaryString(i); int bValueSize = bValue.length(); for (int k = 0; k < (setSize - bValueSize); k++) { bValue = "0" + bValue; } System.out.print("{ "); for (int j = 0; j < setSize; j++) { if (bValue.charAt(j) == '1') { System.out.print((s.get(j)) + " "); } } System.out.print("} "); } } } //Output : { } { 8 } { 5 } { 5 8 } { 9 } { 9 8 } { 9 5 } { 9 5 8 } 

Answer 10

这是一些伪代码。 您可以通过随时随地存储每个呼叫的值并在recursion呼叫检查之前（如果呼叫值已经存在）来削减相同的recursion调用。

以下algorithm将具有排除空集的所有子集。

 list * subsets(string s, list * v){ if(s.length() == 1){ list.add(s); return v; } else { list * temp = subsets(s[1 to length-1], v); int length = temp->size(); for(int i=0;i<length;i++){ temp.add(s[0]+temp[i]); } list.add(s[0]); return temp; } } 

Answer 11

 public static ArrayList<ArrayList<Integer>> powerSet(List<Integer> intList) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); result.add(new ArrayList<Integer>()); for (int i : intList) { ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>(); for (ArrayList<Integer> innerList : result) { innerList = new ArrayList<Integer>(innerList); innerList.add(i); temp.add(innerList); } result.addAll(temp); } return result; }