java递归查找所有子集
我不知道这个代码是怎么工作的,你能解释一下吗
// A Java program to print all subsets of a set
import java.io.IOException;
import java.util.Scanner;
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("{ ");
// 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)
{ Scanner in = new Scanner(System.in);
char[] set = in.nextLine().replaceAll("[?!^]","").toCharArray();
//char[] set = in.nextLine().split("(?!^)").toCharArray();
//char set[] = {'a', 'b', 'c'};
printSubsets(set);
in.close();
}
}
基本上我不能递归思考,我有问题,如果有什么我能做的,请告诉我
# 1 楼答案
此代码打印符号的所有子集。 假设字符串包含N个符号,每个符号都是唯一的。然后,为了生成子集,我们可以包含/排除每个符号——这为一个位置提供了两个组合;对于N个符号,我们将它们全部相乘,然后得到2^N个组合
例如:abcd 我们可以将子集{a,b,c}->;1110; {a,d}->;1001; {b} ->;0100; {}->;0000; 等等
1<&书信电报;N-是给出2^N(或N位数字)的位运算
(1<;<;j)-在第j位中获取1
(i&;(1<;<;j))-检查数字中的第j位
此外,这个程序不是递归的——它是线性的,用循环完成