import java.util.Stack;

 class Test {

    public static void main(String[] args) {
		int[] input = { 1, 2, 3, 4, 5 };
		ma(input);
	}

	public static void ma(int[] input) {
		Stack<Boolean> stack = new Stack<>();
		while (true) {
			while (stack.size() < input.length) {
				stack.push(true);
				print(stack, input);
			}
			while (!stack.isEmpty() && !stack.peek())
				stack.pop();
			if (stack.isEmpty())
				break;
			stack.pop();
			stack.push(false);
		}
	}

	public static void print(Stack<Boolean> stack, int[] input) {
		boolean begin = true;
		for (int i = 0; i < stack.size(); i++)
			if (stack.get(i)) {
				if (begin)
					begin = false;
				else
					System.out.print(' ');
				System.out.print(input[i]);
			}
		System.out.println();
	}
}