Sets of numbers that sum to a certain number

This isn't (IMO) a very interesting problem from a programming point of view. You could come up with a recursive algorithm that tries every arrangement, something like this:

bool try_queens(Board board, int n)
{
    if (n == 0) {
        // no queens left to place, so we're done
        return true
    }
    // try each open position until we find one that works
    for each position on the board {
        if (is_empty(board, position) and not is_attacked(board, position)) {
            place_queen(board, position)
            if (try_queens(board, n-1)) {
                return true
            }
            remove_queen(board, position)
        }
    }
    // if we get this far, there's no available position
    return false
}

main()
{
    initialize board(X,Y)
    return try_queens(board, N)
}

If you think about the problem a bit, you'll realize that there's no way to fit N queens on a board where X < N or Y < N because that would require that at least two queens end up in the same rank or file, and they would therefore attack each other. If you read about the n-queens problem, you'll quickly learn that it's always possible to place N queens on a NxN board for N > 3. Now we know that the answer is NO for (X < N or Y < N) and YES for (X >= N and Y >= N, N > 3). All that's left are the special cases:

• N=1 (YES)
• N=2 (YES for X>=2 and Y>2 or vice versa)
• N=3 (YES for X>=3 and Y>3 or vice versa)

So now our nice recursive function becomes a simple function that just compares N to X and Y and returns a canned result. That's great from a performance point of view, since you can get an answer in constant time. It's not so great from a programming point of view because you realize, at this point, that the question is really more about how well you can solve puzzles than it is about your ability to write a recursive function.

(And boy oh boy, I really hope that I didn't make some dumb mistake in my smarty-pants answer. ;-)

Let's say k is the number of highest numbers you want to know (100 in your example). Then, you can add a new number in O(k) which is also O(1). Because O(k*g) = O(g) if k is not zero and constant.