如何生成可變長度集的所有子集？

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。