The task is to generate all possible combinations of r distinct numbers from the set {1, 2, ..., n}. A combination is an unordered selection, meaning {1, 2, 3} is the same as {3, 2, 1}. We need to print each combination on a new line, with numbers sorted in ascending order and each number occupying exactly three characters of space. The combinations themselves should be printed in lexicographical order.

A powerful technique for this problem is backtracking, which can be implemented using recursion. The core idea is to build the combinations step-by-step. At each step, we decide whether to include the next number in the sequence. This creates a decision tree where each path represents a potential combination. We traverse this tree, and when we reach a path with r numbers, we have found a valid combination and print it.

Python Implementation

def generate_combinations(n, r):
    """
    Generates all combinations of r numbers from 1 to n using backtracking.
    """
    result = []
    current_combination = []

    def backtrack(start, depth):
        # If the combination is complete, format and add it to the results
        if depth == r:
            formatted_combination = ' '.join(f"{num:3d}" for num in current_combination)
            result.append(formatted_combination)
            return

        # If we've run out of numbers to choose from, stop this path
        if start > n:
            return

        # 1. Choose the current number 'start'
        current_combination.append(start)
        backtrack(start + 1, depth + 1)
        # Backtrack: remove the number to explore the "not chosen" path
        current_combination.pop()

        # 2. Do not choose the current number 'start'
        backtrack(start + 1, depth)

    backtrack(1, 0)
    return result

# Main execution
if __name__ == "__main__":
    n, r = map(int, input().split())
    combinations = generate_combinations(n, r)
    for combo in combinations:
        print(combo)