import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class StairsClimbing {

	public static void main(String[] args) {
		Solver sv = new StairsClimbing().new Solver(4);
		System.out.println("Anzahl Möglichkeiten: "+ sv.getSolutionCount());
		System.out.println("Lösungen: "+ sv.getSolutions());
	}

	class Solver {

		private List<String> solutions = null;

		public Solver(int stairsCount) {
			this.solutions = new ArrayList<String>();
			this.doIt(stairsCount, prepareString(stairsCount));
		}

		private String prepareString(int stairsCount) {
			char[] array = new char[stairsCount];
			Arrays.fill(array, '1');
			return String.valueOf(array);
		}

		private void doIt(int pos, String stairs) {
			for(int i=pos; i>1; i--)
				doIt(i-2, stairs.substring(0,i-2) +"2"+ stairs.substring(i));
			solutions.add(stairs);
		}

		public String getSolutions() {
			Collections.reverse(solutions);
			String resultString = Arrays.toString(solutions.toArray());
			return resultString.substring(1, resultString.length()-1);
		}
		
		public int getSolutionCount() {
			return solutions.size();
		}

	}

}

Anzahl Möglichkeiten: 5
Lösungen: 1111, 211, 121, 112, 22