Python 2, 75 * 0.5 = 37.5

N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

Python 2, 72 bytes * 0.5 = 36

N=1<<input()
for k in range(N*N):
 if bin(k%N).count('1')==k/N:print k%N

Try it online!

A new method for this now-ancient challenge. The less-golfed below below might be easier to understand:

87 bytes

n=input()
for i in range(n+1):
 for x in range(2**n):
  if bin(x).count('1')==i:print x

Try it online!

We loop over target popcounts i in increasing order, and for each one iterate over the n-bit numbers and prints those with exactly i set bits.

Even though this loops over the n-bit numbers many times, it still satisfies the efficiency bonus criteria of only using O(n) memory if the loop were converted to a generator. If fact, the golfed code allocates n bits to the target popcount as well as n bits to the number being checked. They are stored as a 2*n-bit number, which allows counting up this single number and extracting the first and last n bits as needed.

Python 2, 59 bytes

lambda n:sorted(range(1<<n),key=lambda x:bin(x).count('1'))

Try it online!

A short sorting-based approach that does not qualify for the bonus.

Python 2, 75 bytes * 0.5 = 37.5

N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Try it online!

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

Python 2, 75 * 0.5 = 37.5

N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

Python 2, 75 * 0.5 = 37.5

N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

Python 2, 76 * 0.5 = 38

N=2**input()-1
v=N*2+1
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

Python 2, 75 * 0.5 = 37.5

N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15