查找Java中给定集合的所有子集

淩亂°似流年 2023-10-04 08:26 25阅读 0赞

**问题：**找到给定集合的所有子集。

输入： 
    S = {a，b，c}
    输出：
    {}，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}，

任何给定集合的子集总数等于2 ^（集合中元素的数量）。如果我们仔细地注意到，它不过是从0到7的二进制数，可以显示如下：

从右开始，第i个位置的1表示该集合的第i个元素存在，0表示该元素不存在。因此，我们要做的只是生成从0到2 ^ n – 1的二进制数，其中n是集合的长度或集合中元素的数目。

//A Java program to print all subsets of a set 
    
    class Main {
    	// Print all subsets of given set[]
    	static void printSubsets(char set[]) {
    		int n = set.length;
    
    		// Run a loop for printing all 2^n
    		// subsets one by one
    		for (int i = 0; i < (1 << n); i++) {
    			System.out.print(1 << n);
    			System.out.print("{ ");
    
    			// Print current subset
    			for (int j = 0; j < n; j++)
    
    				// (1<<j) is a number with jth bit 1
    				// so when we 'and' them with the
    				// subset number we get which numbers
    				// are present in the subset and which
    				// are not
    				if ((i & (1 << j)) > 0)
    					System.out.print(set[j] + " ");
    
    			System.out.println("}");
    		}
    	}
    
    	// Driver code
    	public static void main(String[] args) {
    		char set[] = { 'a', 'b', 'c' };
    		printSubsets(set);
    	}
    }

<< : 左移运算符，num << 1,相当于num乘以2，上面代码中1<< n,将1左移n位相当于2的n次方

>> : 右移运算符，num >> 1,相当于num除以2

>>> : 无符号右移，忽略符号位，空位都以0补齐

输出：

{ }
    { a }
    { b }
    { a b }
    { c }
    { a c }
    { b c }
    { a b c }