シフト演算を使ったプログラムの間違い探し(python)

Question

シフト演算を使ったプログラムの間違い探し

問題文
N 枚のカードがあり、左から i 番目のカードには整数 A iが書かれています。
カードを 5 枚選ぶ方法のうち、選んだカードに書かれた整数の和がちょうど 1000 となるものは何通りありますか。

入力例：
13
243 156 104 280 142 286 196 132 128 195 265 300 130
出力:
4

という問題をシフト演算の練習を兼ねて解こうとしていました。
(for文を5回まわせば簡単に実装できますが、今回はシフト演算でやっています。)

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for bit in range(0, 1 << len(A)):
  flag = list()
  sum = 0
  for i in range(0, len(A)):
    if bit & 1 << i:
      flag.append(i)
  for j in range(0, len(flag)):
    sum += A[flag[j]]
  if sum == 1000:
    cnt += 1
print(cnt)

このコードでできるかと思いきや、
13
243 156 104 280 142 286 196 132 128 195 265 300 130
(7通り)
となってしまいます。
どこが間違っているのでしょうか？

一応
bitの数は2^len(A)となっていて大丈夫そう。

len(A) = 3ときにflagを見ていたら
[]
[0]
[1]
[0,1]
[2]
[0,2]
[1,2]
[0,1,2]
みたいな感じですべての組み合わせで取れていました。

ちなみに

for bit in range(0, 1 << len(A) - 1):

とすると
(4)が出力されるのですが、
自動採点システムでは答えが間違っていることがあるということで根本的な解決にはなっていないようです。
自動採点システムではどのような入力の時に間違っているのかは見れず、ただ間違った答えが出力されていることしかわかりません。

Answer 1

カードを「5枚」選ぶって書いてある。いまの全bit列挙の場合、6枚とか4枚の場合があるのでNG

Comments

[ryomannn]

そうですね...ありがとうございます。