如何生成可变长度集的所有子集？

Question

我正试图编写一个程序来生成java中输入集合的所有子集。我想我几乎有它的工作。

• 我必须使用数组（不是数据结构）
• 输入的阵列将永远不会大于20

现在，当我运行我的代码，这是我所得到的：

Please enter the size of A: 3 
Please enter A: 1 2 3 
Please enter the number N: 3 
Subsets: 
{ } 
{ 1 } 
{ 1 2 } 
{ 1 2 3 } 
{ 2 3 } 
{ 2 3 } 
{ 2 } 
{ 1 2 } 

这是子集（2 ^大小）的正确数目，但你可以看到它打印几个副本，而不是某些子集。

任何想法，我错了我的代码？

import java.util.Scanner; 

public class subSetGenerator 
{ 
    // Fill an array with 0's and 1's 
    public static int [] fillArray(int [] set, int size) 
    { 
     int[] answer; 
     answer = new int[20]; 

     // Initialize all elements to 1 
     for (int i = 0; i < answer.length; i++) 
      answer[i] = 1; 

     for (int a = 0; a < set.length; a++) 
      if (set[a] > 0) 
       answer[a] = 0; 

     return answer; 
    } // end fill array 

    // Generate a mask 
    public static void maskMaker(int [] binarySet, int [] set, int n, int size) 
    { 
     int carry; 
     int count = 0; 
     boolean done = false; 

     if (binarySet[0] == 0) 
      carry = 0; 

     else 
      carry = 1; 

     int answer = (int) Math.pow(2, size); 

     for (int i = 0; i < answer - 1; i++) 
     { 
      if (count == answer - 1) 
      { 
       done = true; 
       break; 
      } 

      if (i == size) 
       i = 0; 

      if (binarySet[i] == 1 && carry == 1) 
      { 
       binarySet[i] = 0; 
       carry = 0; 
       count++; 
      } // end if 

      else 
      { 
       binarySet[i] = 1; 
       carry = 1; 
       count++; 
       //break; 
      } // end else 

      //print the set 
      System.out.print("{ "); 

      for (int k = 0; k < size; k++) 
       if (binarySet[k] == 1) 
        System.out.print(set[k] + " ");    

      System.out.println("}"); 

     } // end for 

    } // maskMaker 

    public static void main (String args []) 
    { 
     Scanner scan = new Scanner(System.in); 
     int[] set;   
     set = new int[20]; 
     int size = 0; 
     int n = 0; 

     // take input for A and B set 
     System.out.print("Please enter the size of A: "); 
     size = scan.nextInt(); 

     if (size > 0) 
     { 
      System.out.print("Please enter A: "); 
      for (int i = 0; i < size; i++) 
       set[i] = scan.nextInt(); 
     } // end if 

     System.out.print("Please enter the number N: "); 
     n = scan.nextInt(); 

     //System.out.println("Subsets with sum " + n + ": "); 
     System.out.println("Subsets: "); 

     System.out.println("{ }"); 
     maskMaker(fillArray(set, size), set, n, size); 

    } // end main 

} // end class 

Answer 1

的i值始终从0到N-1，然后返回到0。这是没有用的产生，你只需要一次每隔二进制掩码。如果您仔细考虑，只有当您生成所有可能的掩模（最多为i-1）时，才需要移动i。

还有就是要做到这一点更简单的方法，如果你记得每一个数码已在内部在计算机的二进制表示的，每次你增加它的Java是做加法，并通过自身携带。寻找bitwise operators。