Brute Force for TechJob by bleed1979

gistfile1.java

package com.gmail.at.bleed1979;

import java.util.ArrayList;
import java.util.Collections;

public class BF {
	public static void main(String[] args) {
		final int TARGET = 100;
		for(int i = 6; i <= TARGET; ++i) {
			System.out.println("round" + i);
			ArrayList<Integer> AL = new ArrayList<Integer>();
			for(int j = 1; j <= i; ++j) {
				AL.add(new Integer(j));
			}
			
			while(true) {
				int total_weight = 0;
				for(int j = 0; j < AL.size(); ++j) {
					total_weight += AL.get(j).intValue();
					System.out.print(AL.get(j).intValue() + " ");
				}
				System.out.println();
				if(total_weight >= TARGET) {
					int j = 1;
					ArrayList<Integer> newAL = null;
					for(; j <= TARGET; ++j) {
						newAL = new ArrayList<Integer>();
						int k = j;
						boolean flag = true;
						while(flag && k > 0) {
							flag = false;
							for(int x = AL.size() - 1; x >= 0; --x) {
								int this_weight = AL.get(x).intValue();
								if(k >= this_weight) {
									k -= this_weight;
									newAL.add(new Integer(this_weight));
									AL.remove(x);
									flag = true;
									break;
								}
							}
						}
						AL.addAll(newAL);
						Collections.sort(AL);
						if(k > 0) {
							break;
						}
					}
					if(j > TARGET) {
						System.out.println("Solved!");
						for(Integer al : newAL) {
							System.out.print(al.intValue() + " ");
						}
						System.out.println();
						return;
					}
				}
				boolean well_done = false;
				while(!well_done) {
					int j = AL.size() - 1;
					for(; !well_done && j >= 0; --j) {
						int this_weight = AL.get(j).intValue() + 1;
						if(this_weight <= TARGET) {
							AL.set(j, new Integer(this_weight));
							int k = j + 1;
							for(; k < AL.size(); ++k) {
								int next_weight = AL.get(k - 1).intValue() + 1;
								if(next_weight > TARGET) {
									break;
								}
								AL.set(k, new Integer(next_weight));
							}
							well_done = (k == AL.size());
						}
					}
					if(j < 0) {
						break;
					}
				}
				if(!well_done || AL.get(0).intValue() != 1 || AL.get(1).intValue() != 2) {
					break;
				}
			}
		}
	}
}