java_test/subsets.java at master · codehoper/java_test · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package com.ub.test;

class subsets
{
	static boolean finished = false;
	static final int MAXCANDIDATES = 100;
	static final int NMAX = 100;
	static void backtrack(boolean a[], int k, int input)
	{
		boolean c[] = new boolean [MAXCANDIDATES];
		int ncandidates, i;
		if (is_a_solution(a,k,input)) // first  elements of vector  are a complete solution for the given problem
			process_solution(a,k,input);
		else
		{
			k++;
			ncandidates = construct_candidates(a,k,input,c);
			for (i=0; i<ncandidates; i++) {
				a[k] = c[i];
//				make_move(a,k,input);
				backtrack(a,k,input);
//				if (finished) return;
//				unmake_move(a,k,input);
			}
		}
	}
//	static void make_move(boolean a[],int k,int n)
//	{
//	}
//	static void unmake_move(boolean a[],int k,int n)
//	{
//	}
	static void process_solution(boolean a[],int k, int n)
	{
		System.out.printf("{");
		for(int i=1;i<=k;i++)
			if(a[i])
				System.out.printf(" %d",i);
		System.out.printf(" }\n");
	}
	static boolean is_a_solution(boolean a[],int k,int n)
	{
		return k==n;
	}
	static int construct_candidates(boolean a[],int k,int n,boolean c[])
	{
		c[0] = true;
		c[1] = false;
		return 2;
	}
	static public void main(String[] args)
	{
		boolean a[] = new boolean[NMAX];
		backtrack(a,0,3);
	}
}