子集生成

输入：3

输出：1

          1 2 

          1 2 3

          2

          2 3

          3

位向量法：

public class Main {

	static int[] a;

	public static void fun(int cur, int n) {
		if (cur == n) {
			for (int i = 0; i < cur; i++) {
				if (a[i] == 1)
					System.out.print(i + 1);
			}
			System.out.println();
			return;
		}
		a[cur] = 1;// 选当前元素
		fun(cur + 1, n);
		a[cur] = 0;// 不选当前元素
		fun(cur + 1, n);
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		a = new int[100];
		while (in.hasNext()) {
			int n = in.nextInt();
			fun(0, n);
		}
	}
}

增量构造法：

一次选出一个元素放到集合

public class Main {

	static int[] a;

	public static void fun(int cur, int n) {
		for (int i = 0; i < cur; i++) {
			System.out.print(a[i] + " ");
		}
		if (cur != 0)
			System.out.println();
		int min = cur > 0 ? a[cur - 1] + 1 : 1;// 确定当前元素的最小可能值
		for (int i = min; i <= n; i++) {
			a[cur] = i;
			fun(cur + 1, n);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		a = new int[100];
		while (in.hasNext()) {
			int n = in.nextInt();
			fun(0, n);
		}
	}
}